阅读量:0
文章目录
1.AVL树
在前面，我们已经介绍过了二叉搜索树，也了解到二叉搜索树查找的效率非常的高。但是在数据有序或接近有序时，它就会退化成单边树，那样效率就变得非常低了。所以我们也一直说二叉搜索树的搜索的时间复杂度是O(N)(高度次)，并不是O(log2N)。
因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
1.1 AVL树的概念
由于二叉搜索树可能会退化，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
为什么要求左右子树的高度之差不超过1就可以呢？
对于所有形状的子树来说，如果他有2n-1个节点，那它就可以保持绝对的平衡；如果他有2n (n >= 1)个节点，就无法做到绝对的平衡，最好的结果就是子树高度相差一。
一棵AVL树要么是空树，要么是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果他有n个节点，其高度可保持在log2N，搜索的时间复杂度就是log2N。
1.2 AVL树节点的定义
为了方便确认一棵树是否是AVL树，我们在节点中定义一个平衡因子，通过它来记录每棵树左右子树的高度。
如果右子树比左子树高一层，那平衡因子就是1；如果左右子树一样高，那平衡因子就是0；如果左子树比右子树高一层，那平衡因子就是-1。此时AVL树的性质都没有被打破。
当左子树比右子树高两层，那平衡因子就是-2；或者右子树比左子树高两层，平衡因子就是2，此时AAVL树的性质就被打破了，需要调整。
在调整失衡的AVL树时，我们需要频繁的访问其父节点，因此我们给每个节点定义一个指向父亲的指针
template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; //存放数据 AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _prev; //指向当前节点的父亲 int _bf;//平衡因子 AVLTreeNode(const pair<K,V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,prev(nullptr) ,_bf(0) {} }; 1.3 AVL树的插入
AVL树的插入与普通二叉搜索树的插入基本一致。唯一的区别就是AVL树插入节点后需要判断AVL树是否失衡，存在失衡就需要调整。
我们平衡因子是使用右子树的高度-左子树的高度，因此，如果新节点插入到父节点的右边，那父亲的平衡因子+1；如果新节点插入到父亲节点的左边，那父亲的平衡因子-1。
对于情况二来说，新节点的插入不会影响其祖先的平衡因子的改变，因为子树的高度没有改变。
对于情况一来说，新节点的插入会影响其祖先的平衡因子的改变，因为子树的高度变高了。
所以，对于情况一来说，我们新插入节点后，还要观察其祖先的平衡因子是否变化，变化后是否需要调整。
那么下面我们就先将节点插入到树中：
bool insert(const pair<K, V>& kv) { //插入前是空树 if (_root == nullptr) { //新插入的节点就是根 _root = new Node(kv); _root->_prev = nullptr; return true; } else { Node* cur = _root; Node* parent = nullptr; //寻找插入位置 while (cur) { if (cur->_kv.first < kv.first) { parent = cur;//记录父节点，以便后序连接 cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false;//节点已经存在，插入失败 } } //已找到了插入位置 cur = new Node(kv); //判断连接在父亲的哪一侧 if (parent->_kv.first < kv.first) parent->_right = cur; else parent->_left = cur; cur->_prev = parent;//指向父亲 //判断树是否失衡 //... } } 更新父亲/祖先的平衡因子
//判断树是否失衡 while (parent) { //更新父亲的平衡因子 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 = cur->_prev; } else if (parent->_bf == 2 || parent->_bf == -2) { //旋转处理 break; } else { assert(false);//平衡因子异常了 } } 1.4 AVL树的旋转
AVL树的旋转分为四种情况：
- 左单旋
- 右单旋
- 左右双旋
- 右左双旋
下面，我们对这四种情况具体分析
1.4.1 左单旋
新节点插入到较高右子树的右侧- -左单旋
在旋转过程中，有以下几种情况需要考虑：
- 7节点的左孩子可能存在，也可能不存在
- 6可能是根节点，也可能是子树
- 如果是根节点，旋转完成后，根节点就是7
- 如果是子树，可能是某个节点的左子树，也可能是右子树，需要判断以后连接
void RotateL(Node* parent) { Node* subR = parent->_right;//父亲的右孩子 Node* subRL = subR->_left;//右孩子的左孩子 //升高度，连孙子 parent->_right = subRL; if (subRL) subRL->_prev = parent; Node* parentPrev = parent->_prev; //降高度，变父亲 subR->_left = parent; parent->_prev = subR; //连接旋转后的子树 subR->_prev = parentPrev; if (parentPrev == nullptr) { //如果原父亲就是根，旋转后的儿子变根 _root = subR; } else { //原父亲是子树，判断儿子连接在哪一边 if (parentPrev->_left == parent) parentPrev->_left = subR; else parentPrev->_right = subR; } //更新平衡因子 subR->_bf = 0; parent->_bf = 0; } 1.4.2 右单旋
新节点插入到较高左子树的左侧- - 右旋
在旋转过程中，有以下几种情况需要考虑：
- 5节点的右孩子可能存在，也可能不存在
- 6可能是根节点，也可能是子树
- 如果是根节点，旋转完成后，根节点就是5
- 如果是子树，可能是某个节点的左子树，也可能是右子树，需要判断以后连接
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; //升高度，连孙子 parent->_left = subLR; if (subLR) subLR->_prev = parent; Node* parentPrev = parent->_prev; //降高度，变父亲 subL->_right = parent; parent->_prev = subL; //新父亲指向前 subL->_prev = parentPrev; if (nullptr == parentPrev) { //如果原父亲就是根，旋转后的儿子变根 _root = subL; } else { //原父亲是子树，判断儿子连接在哪一边 if (parentPrev->_left == parent) parentPrev->_left = subL; else parentPrev->_right = subL; } subL->_bf = 0; parent->_bf = 0; } 1.4.3 右左双旋
新节点插入到较高右子树的左侧- -右左双旋
所以，为了解决这种情况，我们可以将这种歪脖树先变成一棵单边树，然后再进行单旋即可。
为了满足所有情况，我们下面使用抽象图再画一遍
观察上图我们可以发现，双旋就是一种抛弃自己的孩子，独自登基的感觉，因此对于旋转后平衡因子的改变，取决于新节点插入到哪一边，最后又到哪里去。
void RotateRL(Node* parent) { //由于单旋会改变节点的位置以及平衡因子，所以提前记录 Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); //修改平衡因子 if (bf == 0)//subRL插入前是空 { parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else if (bf == 1)//subRL之前是一棵树，新节点插入其 右侧 { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else //subRL之前是一棵树，新节点插入其 左侧 { parent->_bf = 0; subR->_bf = -1; subRL->_bf = 0; } } 
1.4.4 左右双旋
新节点插入到较高左子树的右侧–左右双旋
最简单的情况，2的右子树插入前为空
抽象图
跟右左双旋基本一样，这里就不赘述了，咱们直接开旋。
平衡因子的改变也需要小心。
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 0) // subLR插入前为空 { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) //subLR是一棵树，新节点插入到树的 右侧 { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else //subLR是一棵树，新节点插入到树的 左侧 { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } } 
下面就是更新平衡因子的整体思路：
//判断树是否失衡 while (parent) { //更新父亲的平衡因子 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 = cur->_prev; } else if (parent->_bf == 2 || parent->_bf == -2) { //旋转处理 //左单旋 // p cur // cur ---> p new // new if (parent->_bf == 2 && cur->_bf == 1) RotateL(parent); //右单旋 // p cur // cur ---> new p // new else if (parent->_bf == -2 && cur->_bf == -1) RotateR(parent); //右左双旋 // p p cur // cur --> cur --> p new // new new else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent); //左右双旋 // p p cur // cur --> cur --> new p // new new else if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent); else assert(false); break;//旋转后，以parent为根的树已经平衡，无需继续向上更新 } else { assert(false);//平衡因子异常了 } 总结：
假如以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2，分以下情况考虑
- Parent的平衡因子为2，说明Parent的右子树高，设Parent的右子树的根为SubR
- 当SubR的平衡因子为1时，执行左单旋
- 当SubR的平衡因子为-1时，执行右左双旋
- Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树的根为SubL
- 当SubL的平衡因子为-1是，执行右单旋
- 当SubL的平衡因子为1时，执行左右双旋
旋转完成后，原Parent为根的子树个高度降低，已经平衡，不需要再向上更新。
1.5 AVL树的平衡验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
- 验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
- 验证其为平衡树
- 每个节点子树高度差的绝对值不能超过1
- 节点的平衡因子是否计算正确
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 _isBalanceTree() { return isBalanceTree(_root); } bool isBalanceTree(Node* root) { if (root == nullptr)//空树也是平衡二叉搜索树 return true; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); int gap = rightHeight - leftHeight; //计算root的平衡因子 // 如果计算出的平衡因子与root的平衡因子不相等，或者 //root平衡因子的绝对值超过1，则一定不是AVL树 if (gap != root->_bf || (gap > 1 || gap < -1)) { return false; } return isBalanceTree(root->_left) && isBalanceTree(root->_right); } 
1.6 AVL树的删除
- 因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除
- (分析有无左右孩子，若仅有一个孩子，则直接将删除节点连接孩子；若有两个孩子，将删除节点替换为删除节点的左子树的最大或右子树的最小)
- 然后再更新平衡因子，只不过与插入不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
1.7 AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log2N。
但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
