AVL树的特性和模拟实现

AVL树的引入：当二叉搜索树接近有序或者完全有序的时候，就会退化为单边树，这样查找效率极低O（N），
如何解决呢？ ：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。 它的查找效率就是O（logN）

AVL树的节点 和 AVL树的框架

template<class T, class V>
struct AVLTreeNode
{
	AVLTreeNode<T, V>* _left;
	AVLTreeNode<T, V>* _right;
	AVLTreeNode<T, V>* _parent; //我们设置为三叉连结构，方便向上调整平衡因子

	int _bf;
	pair<K, V> _kv;

	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

template<class T,class V>
class AVLTree
{
	typedef AVLTtreeNode<K, V> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}

	//插入，查找，[]重载 ，，， 等等函数功能

private:
	Node* _root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入 bool Insert(const pair& kv)

1，先按照二叉搜索树的方式进行插入
2，调节平衡因子
3，根据平衡因子决定是否要旋转

		if (_root == nullptr)
		{
			_root = new Node(kv);
		}

		Node* parent = nullptr, *cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

平衡因子如何调节呢？ 平衡因子只与子树的高度有关。 也就是说，右子树的节点增加，平衡因子就会+1，
左子树的节点增加，平衡因子 -1.
对于要保持平衡因子的AVL树来说，任何一个节点的平衡因子只会出现这三种情况：
1， 平衡因子 0 ，平衡—> 不需要调节
2， 平衡因子1或-1 ， 需要向上调节平衡因子，说明新插入节点的父亲都受到了影响
3， 平衡因子为 2 或 -2 ，需要旋转处理。 核心难点就变成了旋转处理

	while (cur)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else
			{
				//需要旋转处理
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

如何去旋转

//需要旋转处理
				if (parent->_bf == 2) //右树高的情况
				{
					if (cur->_bf == 1) //需要左旋处理,新增节点在右数高的右侧
					{
						RotateL(parent);
					}
					else    //右左双旋 ，新增节点在右树高的左侧
					{
						RotateRL(parent);
					}
				}
				else //左树高的情况
				{
					if (cur->_bf == -1) //需要右旋处理
					{
						RotateR(parent);
					}
					else  //需要左右旋的情况
					{
						RotateLR(parent)
					}
				}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

就是分4种情况：
先看两种比较简单的情况
1，如果插入的节点在较高的左子树的左侧 ----> 右单旋 ---->右单旋的实质上：让当前节点（不平衡的）的左树节点做根。
2，如果插入的节点在较高右子树的右侧 ----> 左单旋 ----->左单旋的实质 ： 让当前节点（不平衡的）的右树节点做根。
3，新节点插入较高右子树的左侧 -----> 右左双旋 ----> 向让当前节点的右树节点进行右单旋，然后当前节点进行左单旋
4， 新节点插入较高左子树的右侧—左右------》左右双旋 ---->先让当前节点的左树节点进行左单旋， 然后当前节点进行右单旋

这里以右单旋为例（在较高的左树的左侧插入时）

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
				subL->_parent = parentParent;
			}
			else
			{
				parentParent->_right = subL;
				subL->_parent = parentParent;
			}
		}
		subL->_bf = parent->_bf = 0;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

左单旋（在较高右侧的右树上插入时）

void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//首先处理subRL和parent,防止subRL是空
		parent->_right = subRL;
		if (subRL)  
			subRL->_parent = parent;

		//处理parent 和 subR ，要判断panret是否为根节点的情况
		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
				subR->_parent = parentParent;
			}
			else
			{
				parentParent->_right = subR;
				subR->_parent = parentParent;
			}
		}

		subR->_bf = parent->_bf = 0;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

这里以左右双旋为例：这里其实就是在较高左树的右侧进行插入， 然后的化subLR可以分叉！！！！

分叉后的subLR
下面有两种情况， 另外的一种情况就是只有三个节点， panrent， subL, subLR。 调节平衡因子后都是0

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 0)
		{
			subL->_bf = subLR->_bf = parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

右左双旋

void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf; 

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else
		{
			subRL->_bf = 0;
			subR->_bf = 1;
			parent->_bf = 0;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

判断是不是AVL树

     bool isbanlancetree()
	{
		return _isbanlancetree(_root);
	}

     //求root节点的深度。
    int _height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int leftheight = _height(root->_left);
		int rightheight = _height(root->_right);

		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
	}

	bool _isbanlancetree(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftheight = _height(root->_left);
		int rightheight = _height(root->_right);

		if (rightheight - leftheight != root->_bf)
		{
			cout << "banlance factor is fasle" << endl;
			
			return false;
		}

		return abs(rightheight - leftheight) < 2
			&& _isbanlancetree(root->_left)
			&& _isbanlancetree(root->_right);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

AVL树总结

核心在于 ： 画图 画图！！！！
步骤总结 ：
1 按二叉排序的形式进行插入
2 调节平平衡因子
如果0 break -1或1 继续向上调整 2或-2 旋转调整后 break