前言
本文章将会模拟实现一棵AVL树。
以下是本篇文章正文内容
一、什么是AVL树？
AVL树也是一个二叉搜索树，只不过是在二叉搜索树的基础上，增加了一个条件：
任意一棵子树的左右高度差的绝对值不大于1。
设计AVL树的原因
在二叉平衡搜索树中，在正常情况下，对该树的任意节点进行查找，最多查找OlogN次，但如果在极端情况下，该树退化成了单只树，则会极大降低搜索效率，变成O(n)，所以为了避免让二叉搜索树出现极端情况，设计出一棵具有平衡性质的二叉搜索树：AVL树
二、AVL树的性质
- 1）它的左右子树都是AVL树
- 2）左右子树高度之差（平衡因子）的绝对值不超过1（-1/0/1）
平衡因子：右子树高度 - 左子树的高度（注意是右 - 左）
由此可知，一棵AVL树是高度平衡的，它的高度可保持在logN，所以搜索效率可以保持在logN
三、二叉树节点的定义
template<class K, class V> class AVLTreeNode { public: AVLTreeNode(const pair<K, V> kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf; };
- 1）需要有一个平衡因子存在，即
_bf - 2）_data值可以是一个键值对，也可以是其他类型，这里我选择了
pair。 - 3）在后面的其他操作中，会频繁用到一个节点的父亲，所以直接在节点中添加一个
_parent成员。
四、AVL树的插入
插入大致分为几个步骤：
如果根节点为空，则直接插入到根节点的位置
1）先找到插入位置，因为这是一棵搜索树，如果该节点的值比根小，则往左走，如果比根大，往右边走。
2）找到待插入位置后，插入该节点，然后调整平衡因子。
如果插入的是左边，则parent的平衡因子–，如果插入的是右边，则parent的平衡因子++。
如果parent的平衡因子是1或-1，说明父亲的子树有一边高了，则需要继续向上调整。(最坏情况就是调整平衡因子到根的位置)
如果parent的parent的平衡因子大于1或者小于-1了，则不满足AVL树的特性，需要进行旋转。
旋转
1）右单旋
新插入的节点在根节点的左侧，导致根节点的平衡因子变成-2。
则需要将根节点进行右旋。
规则如下：
- 1）cur的right给parent的left
- 2）parent变成了cur的right
调整后，cur变成了新的根，parent变成cur的right
此时需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。
如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。
调整后cur和parent的平衡因子变成0。
2）左单旋
新插入的节点在根节点的右侧，导致根节点的平衡因子变成2。
则需要将根节点进行左旋。
规则如下：
- 1）cur的left给parent的right
- 2）parent变成了cur的left
调整后，cur变成了新的根，parent变成curr的left
此时需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。
如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。
调整后cur和parent的平衡因子变成0。
3）左右双旋
插入新节点后，如果cur的平衡因子为1，parent的平衡因子为-2
说明整颗树的结构大概是这样的：
这就说明，此时这棵树不再是AVL树，所以我们需要对其进行旋转。
旋转操作如下：
- 1）让cur的右指向curright的左，然后cur成为curright的左。此时curright的父亲就变成了原来的cur的父亲，cur的父亲变成了curright
以上操作是左旋的操作过程
- 2）让parent的左指向curright的右，然后parent变成了curright的右，此时parent的父亲变成了curright。
以上操作是右旋的操作过程
这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后curright变成新的根，需要替代parent的位置，变成那个节点的孩子。
平衡因子的处理：
- 1）如果旋转之前，curright的平衡因子是0，则说明，curright这个节点，一定是新插入的节点。
（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。
在进行左右双旋后，cur，curright，parent三个节点的平衡因子都是0。
- 2）如果旋转之前，curright这个节点的平衡因子是-1，该情况就是上图画出的情况，说明新插入节点在curright的左子树，在左右双旋后，cur和curright的平衡因子变成0，parent的平衡因子是1
- 3）如果旋转之前，curright这个节点的平衡因子是1，说明新插入节点在curright的右子树，在左右双旋后，parent和curright的平衡因子变成0，cur的平衡因子是-1
4）右左双旋
插入新节点后，如果cur的平衡因子为-1，parent的平衡因子为2
说明整颗树的结构大概是这样的：
这就说明，此时这棵树不再是AVL树，所以我们需要对其进行右左旋转。
旋转操作如下：
- 1）让cur的左指向curleft的右，然后cur成为curleft的右。此时culeft的父亲就变成了原来的cur的父亲，cur的父亲变成了curleft
以上操作是右旋的操作过程
- 2）让parent的右指向curleft的左，然后parent变成了curleft的左，此时parent的父亲变成了curleft。
以上操作是左旋的操作过程
这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后currleft变成新的根，需要替代parent的位置，变成那个节点的孩子。
平衡因子的处理：
- 1）如果旋转之前，curleft的平衡因子是0，则说明，curleft这个节点，一定是新插入的节点。
（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。
在进行左右双旋后，cur，curleft，parent三个节点的平衡因子都是0。
- 2）如果旋转之前，curleft这个节点的平衡因子是1，该情况就是上图画出的情况，说明新插入节点在curleft的右子树，在右左双旋后，cur和curleft的平衡因子变成0，parent的平衡因子是-1
- 3）如果旋转之前，curleft这个节点的平衡因子是-1，说明新插入节点在curleft的左子树，在右左双旋后，parent和curleft的平衡因子变成0，cur的平衡因子是1
以上就是旋转的四种情况。
AVL树插入完整代码
template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: AVLTree() :_root(nullptr) {} bool Insert(const pair<K,V> kv) { if(_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* cur_parent = _root; //1.找到待插入位置 while (cur) { if (cur->_kv.first < kv.first) { cur_parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { cur_parent = cur; cur = cur->_left; } else return false; } //2.先判断待插入节点是在parent的左边还是右边 cur = new Node(kv); if (cur_parent->_kv.first > kv.first) { cur_parent->_left = cur; } else { cur_parent->_right = cur; } cur->_parent = cur_parent; //下面为调整二叉树的平衡 //1.更新平衡因子 // while (cur_parent) { //左子树-- if (cur_parent->_left == cur) { cur_parent->_bf--; } //右子树++ else { cur_parent->_bf++; } //平衡因子=0，不再影响祖先 if (cur_parent->_bf == 0) { break; } //不平衡了，影响祖先，要向上也调整 else if (cur_parent->_bf == 1 || cur_parent->_bf == -1) { cur = cur_parent; cur_parent = cur_parent->_parent; } //此时该树出问题了，需要旋转进行平衡 else if (cur_parent->_bf == 2 || cur_parent->_bf == -2) { //右边高，向左旋转 if (cur_parent->_bf == 2 && cur->_bf == 1) { RotateL(cur_parent); } //左边高，向右旋转 else if (cur_parent->_bf == -2 && cur->_bf == -1) { RotateR(cur_parent); } //折线型，右边高，右左双旋 else if (cur_parent->_bf == 2 && cur->_bf == -1) { RotateRL(cur_parent); } //折线形，左边高，左右双旋 else if (cur_parent->_bf == -2 && cur->_bf == 1) { RotateLR(cur_parent); } //旋转完成后一定平衡了，则break break; } else { assert(false); } } cout << kv.first << endl; return true; } //左单旋 void RotateL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; Node* ppNode = parent->_parent; parent->_right = curleft; if (curleft) curleft->_parent = parent; cur->_left = parent; parent->_parent = cur; if (!ppNode) { _root = cur; cur->_parent = nullptr; } else { if (ppNode->_right == parent) { ppNode->_right = cur; } else { ppNode->_left = cur; } cur->_parent = ppNode; } cur->_bf = parent->_bf = 0; } //右单旋 void RotateR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; Node* ppNode = parent->_parent; parent->_left = curright; //如果cur的右子树是空 if(curright) curright->_parent = parent; cur->_right = parent; parent->_parent = cur; if (!ppNode) { _root = cur; cur->_parent = nullptr; } else { cur->_parent = ppNode; //要知道根的左边是cur还是右边是cur if (ppNode->_left == parent) { ppNode->_left = cur; } else { ppNode->_right = cur; } } cur->_bf = parent->_bf = 0; } void RotateLR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; int bf = curright->_bf; RotateL(parent->_left); RotateR(parent); //该节点为新插入的节点 if (bf == 0) { curright->_bf = 0; cur->_bf = 0; parent->_bf = 0; } //新插入节点在curright的右边，右边高了 // p // c // cr else if (bf == 1) { curright->_bf = 0; cur->_bf = -1; parent->_bf = 0; } //新插入节点在curright的左边，左边高了 else if (bf == -1) { curright->_bf = 0; cur->_bf = 0; parent->_bf = 1; } } void RotateRL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; int bf = curleft->_bf; RotateR(parent->_right); RotateL(parent); //该节点为新插入的节点 if (bf == 0) { curleft->_bf = 0; cur->_bf = 0; parent->_bf = 0; } //新插入节点在curleft的右边，右边高了 // p // c // cl else if (bf == 1) { curleft->_bf = 0; cur->_bf = 0; parent->_bf = -1; } //新插入节点在curleft的左边，左边高了 else if (bf == -1) { curleft->_bf = 0; cur->_bf = 1; parent->_bf = 0; } } private: Node* _root = nullptr; };
验证一棵树为AVL树
- 1）验证这棵树的中序遍历是有序的。
- 2）验证每一棵树的左右子树高度差不大于1
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 IsBalanceTree() { cout << "IsBalanceTree():"; return _IsBalanceTree(_root); } //通过高度判断是否为AVL树 //1.通过高度计算出真实的平衡因子，再与AVL树本身的平衡因子进行比较 bool _IsBalanceTree(Node* root) { if (root == nullptr) return true; int lefth = Height(root->_left); int righth = Height(root->_right); int bf = righth - lefth; if (bf != root->_bf || bf > 1 || bf < -1) { return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); }
AVL树的性能分析
由于AVL树的绝对平衡（每棵树高度差不大于1），每次在插入数据时，难免会遇到多次旋转，最坏情况需要旋转到根部。虽然旋转时间复杂度O(1)，但如果旋转次数过多，也会造成效率下降。在本文中没有提到AVL树的删除，删除操作更加复杂，我没有研究过hh，不过同样每删除一个数据，都必须保证整棵树是AVL树，这又需要大量旋转来维持它的平衡。
所以在面对大量数据，并且不再有新数据的插入时，可以使用AVL树进行查找，效率为O(logN).
总结
本文主要讲述了AVL树的插入过程及其效率分析。
