C++模拟实现—

C++模拟实现——AVL树

AVL树

1.介绍

AVL树是对搜索二叉树的改进，通过特定的方法使得每个节点的左右子树高度差绝对值不超过1，使得避免出现歪脖子的情况，最核心的实现在于插入值部分是如何去实现平衡调整的，由于前面详细实现和解析过搜索二叉树，因此本篇文章着重整理AVL树核心的部分，插入的实现，以及旋转是如何操作的

2.基本框架

先搭建一个搜索二叉树的基本框架

节点定义部分

平衡因子的概念：

一个节点的平衡因子指的是左右子树的高度差，根据自己定义，可以是左边高度减右边高度，或者是右边高度减左边高度，在AVL树中，调节平衡因子是实现平衡的关键

ps：本篇对平衡因子_bf的定义都是右边减左边

AVL树的框架

3.核心部分

基本框架

插入部分重点还是在于平衡因子的调整部分，前面就不详细分析了

平衡因子的调整

每次插入要保持每个节点的平衡因子绝对值都小于1，则说明整棵树是符合AVL树的规则的，即每个节点的左右子树高度差的绝对值不超过1。

因此，再每次插入一个新的节点时，要考虑每个节点之间平衡因子的变化，通过画图观察发现，当一个新节点插入后，有可能受影响的是其部分或者全部祖先

通过画图观察总结出更新的规律，新增节点后，当新增节点在其父母节点的左边则对父母节点的bf进行--，在右边则进行++（这是因为我们定义bf采用右边减左边），当父母节点bf改变后，如果绝对值为1，那么需要继续向上调整，调整的规则也是，看该节点在其父母节点的左边还是右边，左边则--，右边则++，直到遇到每次调整parent时，parent的bf变为0，则说明不需要调整了，并且插入成功，又或者调整parent时，其bf绝对值等于2，则说明需要对该部分子树进行旋转调整了（降高度）

旋转调整

旋转又分成四种方式，分别是左单旋、右单旋、左右双旋、右左双旋

1.单旋

左单旋，当遇到这种最右边高左边低的时候，采用左单旋，将60位置的左子树给30位置，再由60去取代30原先的位置，形象点看就是，好像吧一个旋钮往左旋转了一样

右单旋，同理就是与左单旋的情况相反，最左边高，右边低，将30的b给60,30取代60的位置

代码实现

从画图上来看，这就是左单旋和右单旋，看似简单，但在转化成代码的时候，要注意几个问题：

1.要注意每个节点的parent指针需要被维护

2.一开始我们就对需要用到的位置，用指针去一一对应的话，要注意中间的那个b是有可能为空的

3.最上面的位置不一定就是根节点，因此在更换掉最上面位置节点的时候，要考虑对其上面是否还有节点进行判断，如果还有节点，则进行进一步链接，为根节点则需要将其parent置空

右单旋同理，需要注意的细节和左旋是一样的，这里给出左单旋和右单旋的代码参考

左单旋代码参考：

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;parent->_right = subRL;if (subRL)subRL->_parent = parent;if (pparent){if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}else{_root = subR;_root->_parent = nullptr;}parent->_bf = subR->_bf = 0;}

右单旋代码参考：

	void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;parent->_left = subLR;if (subLR)subLR->_parent = parent;if (pparent){if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}else{_root = subL;_root->_parent = nullptr;}parent->_bf = subL->_bf = 0;}

2.双旋

双旋是为了解决子树往中间偏的问题，当子树往中间偏高时，可以先将其往一边掰直，转换成上面两种情况之一，然后再调整，因为需要两次单旋操作，所以叫双旋

左右双旋，对30位置进行左旋，然后再对90位置进行右旋，从结果来看就是，将60最终放到最上面，60的左子树给左边的30,60的右子树给了右边90

右左双旋同理

双旋的代码实现：

双旋的难点不是在于实现双旋操作本身，因为只需要复用左单旋和右单旋就可以了，真正的难点在于对平衡因子的更新，与单旋不同，双旋对平衡因子的更新并不是直接将调整位置的值都变成0，而是需要根据实际情况去分类讨论的

拿左右双旋举例

左右双旋代码分析

代码参考：

左右双旋：

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int subLR_bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (subLR_bf == -1)//在b下新增节点{parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (subLR_bf == 1)//在c下新增节点{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (subLR_bf == 0)//subRL就是新增节点{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}

右左双旋：

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);}}

3.根据不同情况选择不同旋转方式

以上，就是AVL树的核心实现，最重要的就是控制平衡，通过旋转调整平衡的方式，保证了每个节点的左右子树绝对值不超过1，实现平衡，大大加快了搜索二叉树的效率，搜索效率能够达到
O(logN）

4.测试接口

中序遍历

中序遍历有序只能保证树是二叉搜索树，但不能保证平衡

	void _InOrder(){InOrder(_root);cout << endl;}void InOrder(const Node* root){if (root == nullptr){return;}InOrder(root->_left);cout << root->_value.first << " ";InOrder(root->_right);}

验证平衡因子是否绝对值不超过1

这里提供一个IsBalanceTree接口验证是否平衡因子绝对值不超过1

	int _Height(){return Height(_root);}int Height(const Node* root){if (root == nullptr)return 0;int left = Height(root->_left) + 1;int right = Height(root->_right) + 1;return left > right ? left:right;}bool _IsBalanceTree(){return IsBalanceTree(_root);}bool IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root) return true;// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (diff != root->_bf || (diff > 1 || diff < -1))return false;// pRoot的左和右如果都是AVL树，则该树一定是AVL树return IsBalanceTree(root->_left) && IsBalanceTree(root -> _right);}

随机值插入验证测试

bool test()
{//16, 3, 7, 11, 9, 26, 18, 14, 15//4, 2, 6, 1, 3, 5, 15, 7, 16, 14srand(time(0));const size_t N = 1000;AVLTree<int, int> n;for (int i = 0; i < N; i++){size_t x = rand()%100;n.Insert(make_pair(x, x));}n._InOrder();return n._IsBalanceTree();
}