数据结构 AVL树_avl树的结点成员有哪些

AVL树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

平衡因子

某结点的右子树与左子树的高度(深度)差即为该结点的平衡因子。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1

实现

结点信息

一个AVL树的结点包含了5个成员，一个是当前节点数据_data，一个是左孩子结点_left，一个是右孩子结点_right，一个是父节点_parent，一个是平衡因子_bf；

template<class T>
struct AVLNode
{
	AVLNode<T>* _parent;
	AVLNode<T>* _left;
	AVLNode<T>* _right;
	T _val;
	int _bf;//平衡因子

	AVLNode(const T& val = T())
		:_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_val(val)
		,_bf(0)//初始化为0，叶子无左右孩子
	{}
};

//AVL树
template<class T>
class AVLTreeNode
{
public:
	typedef AVLNode<T> Node;

private:
	Node* _root;
};
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

插入

1. 查找插入的位置
2. 创建新结点并连接
3. 修改平衡因子，调整成AVL树

第三步要分很多种情况，例如我们拿下图来举例说明

1、假如我们在结点23的左边插入结点20此时此数还是一棵平衡的二叉树，需要修改其父路径上的平衡因子

2、假如我们在结点4的左边插入一个节点3，此时此树还是一棵平衡的树，只需要修改其父节点的平衡因子，因为此结点的插入后，往上追溯的平衡因子修改后为0，并不会对平衡因子为0的父节点的平衡因子造成影响。

3、假如我们在上一幅图中再插入一个节点18。则此时已经不是一棵AVL树了，因为结点23的平衡因子不在[-1, 1]的范围之内。此时需要进行旋转调整
调整前：

调整后

但这种调整只是其中的一种，我们下面看看调整以及如何调整

右单旋

当我们的子树如下图结构时，并且在a处插入一个结点而导致的不平衡，也就是E结点平衡因子小于-1。此时就需要在结点E进行右单旋。

左边的左边高,需要降低左子树的高度，提高右子树的高度。调整后结点S和结点E的平衡因子都为0，其他因子不受影响。

动画演示：中间的一条根为S结点的父节点

需要修改的连接有6条连接，4个结点

右旋核心代码如下：

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

		parent->_left = subLR;
		if (subLR)//如果不为空需要更新_parent
			subLR->_parent = parent;

		if (parent == _root) //父节点为根，则不考虑pparent的连接
		{
			//更新根节点
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			Node* pparent = parent->_parent;
			if (pparent->_left == parent)
				pparent->_left = subL;
			else
				pparent->_right = subL;
			subL->_parent = pparent;
		}
		subL->_right = parent;
		parent->_parent = subL;//必须为最后一个连接

		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

测试：
我们先给出insert的部分代码

	bool insert(const T& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}

		//1.查找到要插入的位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;//记录插入节点的父节点
			if (cur->_val == val)//存在相同节点退出
				return false;
			else if (cur->_val > val)//插入节点比当前节点小，则硬插入当前节点的左子树中
				cur = cur->_left;
			else
				cur = cur->_right;
		}

		//2.连接节点关系
		cur = new Node(val);
		if (parent->_val > val)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;

		//3.修改平衡因子，调整成AVL树
		while (parent)
		{
			//更新父节点的平衡因子，判断是否还平衡
			if (parent->_left == cur)
				--parent->_bf;
			else
				++parent->_bf;

			if (parent->_bf == 0) //表示parent的子树比较短的子树高度+1，不影响parent的父节点的平衡因子，插入完毕
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)//表示parent更新前为0，更新后不为0，树的高度有变，会影响parent的父节点
			{
				//向上追溯修改parent父节点的平衡因子
				cur = parent;
				parent = parent->_parent;
			}
			else if (abs(parent->_bf) == 2)
			{
				if (parent->_bf == -2 && cur->_bf == -1)//左边的左边高
				{
					//右单旋
					RotateR(parent);
				}
				//...
				break;
			}
		}
		return true;
	}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

测试代码：

void test()
{
	AVLTreeNode<int> avl;
	avl.insert(5);
	avl.insert(3);
	//    5
	// 3
	avl.insert(1); //右单旋
	//    3
	// 1     5 
	avl.insert(0);
	avl.insert(2);
	avl.insert(-1);//右单旋
	//右旋前
	//       3
	//    1      5
	//  0  2
	//-1
	//右旋后
	//       1
	//    0      3
	// -1      2   5
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：
执行完insert(1)后

执行完insert(-1)后，以1位根的左右子树

左单旋

当在右子树的右节点中插入一个节点而导致树的平衡因子大于2。此时就需要进行左单旋。应用场景如下

右边的右边高，需要降低右边的高度，从而提高左边的高度。调整后结点S和结点E的平衡因子都为0，其他因子不受影响。

动画演示：中间的一条根为S结点的父节点

连接方式和右单旋非常类似，只是连接的结点不同

左旋代码：

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

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = bullptr;
		}
		else
		{
			Node* pparent = parent->_parent;
			if (pparent->_left == parent)
				pparent->_left = subR;
			else
				pparent->_right = subR;
			subR->_parent = pparent;
		}
		subR->_left = parent;
		parent->_parent = subR;

		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

测试：

void test()
{
	AVLTreeNode<int> avl;
	avl.insert(5);
	avl.insert(3);
	avl.insert(1); //右单旋
	avl.insert(0);
	avl.insert(2);
	avl.insert(-1);//右单旋
	//       1
	//    0      3
	// -1      2   5
	avl.insert(10);
	avl.insert(15); //左单旋
	//左单旋前
	//       1
	//    0      3
	// -1      2   5
	//               10
	//                  15
	//左单旋后
	//       1
	//    0      3
	// -1      2    10
	//             5  15
	avl.insert(20);//左单旋
	//左单旋前
	//       1
	//    0      3
	// -1      2    10
	//            5    15
	//                   20
	//左单旋后
	//			3
	//		1		 10
	//	0     2		5   15
	//-1		     	   20

}
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

走到第一个左单旋后进行旋转后左右子树情况

走到第二个左单旋后进行旋转后左右子树情况

左右双旋 和 右左双旋

左边的右边高，此时需要进行两次旋转，先在C结点进行左旋，再在P结点进行右旋

我们在左旋和右旋旋转完后他们他们的结点的平衡因子都设置为0，可是我们发现p结点旋转完后的平衡因子不是0，所以我们在旋转后完应该要分情况处理。我们再来看看在c子树下插入结点后他们的平衡因子如何

我们发现P结点的平衡因子为0，而C结点的平衡因子为-1。总结下来就是谁拿到高的那边，谁的平衡因子就为0。而没拿到的另一边的高度应该减1

代码：

else if (parent->_bf == -2 && cur->_bf == 1) //左边的右边高
{
	//左右双旋
	Node* subLR = cur->_right;
	int bf = subLR->_bf;
	RotateL(cur);
	RotateR(parent);
	if (bf == -1)
	{
		parent->_bf = 1;
		cur->_bf = 0;
	}
	if (bf == 1)
	{
		parent->_bf = 0;
		cur->_bf = -1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

右边的左边高，此时需要进行两次旋转，先在C结点进行右旋，再在P结点进行左旋

和左右双旋类似，CL结点的平衡因子不同，导致最后P结点和C结点的平衡因子也不同

当在CL结点的右边插入时，C结点的平衡因子为0，P结点的平衡因子为-1；当在CL结点的左边插入结点时，C的结点的平衡因子为1，P结点的平衡因子为0

代码：

else if(parent->_bf == 2 && cur->_bf == -1) //右边的左边高
{
	//右左双旋
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	RotateR(cur);
	RotateL(parent);
	if (bf == 1)
	{
		parent->_bf = -1;
		cur->_bf = 0;
	}
	if (bf == -1)
	{
		parent->_bf = 0;
		cur->_bf = 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码我们都写好了，现在我们就通过验证AVL树来判断我们写的是否正确

总结

当以parent为根的子树不平衡，也就是parent的平衡因子为2或者-2时，会根据不同的平衡原因来进行不同的旋转操作

1. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，右子树的左子树的根为subRL
   1.1 当subR的平衡因子为1时，表示的是右子树的右边高，在parent结点进行左单旋操作
   1.2 当subR的平衡因子为-1时，表示右子树的左边高，此时需要进行右左双旋，也就是以subR结点先进行右单旋，再以parent结点进行左单旋。当subRL的平衡因子为1时，表示在subRL的右边插入新的结点，此时需要更新parent的平衡因子为-1，subR的平衡因子为0；当subRL的平衡因子为-1时，表示在subRL的左边插入新的结点，此时需要更新parent的平衡因子为0，subR的平衡因子为1
2. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，左子树的右子树的根为subLR
   2.1 当subL的平衡因子为-1时，表示左子树的左边高，此时需要进行右单旋
   2.2 当subL的平衡因子为1时，表示左子树的右边高，此时需要进行左右双旋，也就是以subL结点先进行左单旋，再以parent结点进行右单旋。当subLR的平衡因子为1时，表示在subLR的右边插入新的结点，此时需要更新parent的平衡因子为0，subL的平衡因子为-1；当subLR的平衡因子为-1时，表示在subLR的左边插入新的结点，此时需要更新parent的平衡因子为1，subR的平衡因子为0

AVL树的验证

判断AVL树的两个条件

1. 该树是一个二叉搜索树
2. 该树的左右孩子的高度差不能大于1

验证第一个条件可以使用中序遍历来判断，当输出的结果是有序时表示该树为二叉搜索树。我们通过随机值的插入与遍历，来验证该树是否是有序输出

	void inorder()
	{
		_inorder(_root);
		cout << endl;
	}

	void _inorder(Node* root)
	{
		if (root)
		{
			_inorder(root->_left);
			cout << root->_val << " ";
			_inorder(root->_right);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

运行结果：升序输出，该树为二叉搜索树

我们知道一棵树的平衡因子为右子树的高度减去左子树的高度，我们去递归获取子树的高度再利用右左子树高度差比较，相等就继续向下判断，一旦不相等或者平衡因子有误则表示不是AVL树

	bool isBalance()
	{
		cout << endl;
		return _isBalance(_root);
	}

	int height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int left = height(root->_left);
		int right = height(root->_right);

		return left > right ? left + 1 : right + 1;
	}

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

		//查看平衡因子是否和左右子树的高度差一致
		int left = height(root->_left);
		int right = height(root->_right);

		if (right - left != root->_bf || abs(root->_bf) > 1)//不相等或者平衡因子有误则表示不是AVL树
			return false;
		return _isBalance(root->_left) && _isBalance(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

运行结果：该树是一棵AVL树