数据结构进阶：AVL树与红黑树

目录

前言

AVL树

定义

结构

插入

AVL树插入的大致过程

更新平衡因子

旋转 

右单旋

左单旋

左右双旋

右左双旋

实现 

红黑树

定义

性质

结构

插入

实现

总结 

---

前言

在学习了二叉搜索树之后，我们了解到其有个致命缺陷——当树的形状呈现出一边倒的情况时，搜索的效率会退化，由O(logN)退化到O(N)。

为了解决这个问题，前人发明了AVL树和红黑树用以解决这个问题，

二者本质就是时刻注意将树调整为平衡或近似平衡的状态，以保证二叉的结构，从而确保其功能的效率。区别就在于平衡的实现逻辑不同。

AVL树

定义

AVL树是一棵高度平衡的二叉树，要么是一棵空树，

要么是具备以下性质的二叉搜索树：左右子树都是AVL树，左右子树高度差的绝对值<=1。

为了方便计算高度差，我们在实现时引入了平衡因子(balance factor)，用以记录左右子树的高度差。平衡因子 = 右子树高度 - 左子树高度。所以平衡因子的值就只能为0 / 1 / -1；分别表示平衡、右子树高一层、左子树高一层。当然平衡因子不是必须的，但有了它我们能够更好的观察AVL树。

为什么不要求高度差为0呢？显然，假如只有两个结点，就不可能存在此情况。

AVL树因其完全平衡性，使得其效率能够保持在O(logN)，这就是控制平衡的回报，往下我们将学习插入时如何控制平衡。

结构

AVL树是BSTree（二叉搜索树）的改进，所以大体结构与前文是一致的，只不过需要在结点中维护一个平衡因子的变量，可直接参考实现即可。

插入

AVL树插入的大致过程

1.根据二叉搜索树的插入方法插入结点；

2.更新平衡因子；（新增结点影响祖先结点的高度，因此要从下往上更新到根的平衡因子。但未必会走到根，在中间就可能结束，具体情况具体分析）

2.更新过程中检查平衡因子是否有异常，有异常就要进行旋转，否则插入结束。（旋转的本质就是调整平衡，让较高的子树高度下降一层）

更新平衡因子

平衡因子 = 右子树高度 - 左子树高度（即在parent的左子树插入就-1，右子树插入就+1）。

更新后的结果决定是否继续向上更新。

【1】更新后为0，意味着原来是-1->0或1->0，即原来是一边高一边低，并且是在低的位置插入结点，对于parent而言子树高度不变，更新就结束了。

【2】更新后结果为1或-1，则意味着0->1或0->-1，即在parent两边高度相同的情况下插入，插入后仍符合要求，但parent的高度相当于增加1，会影响其祖先的左右子树高度差，于是需要继续向上更新。

【3】更新后结果为2或-2，则意味着1->2或-1->-2，即原来是一边高一边低，却在高的位置插入结点，此时parent的左右子树高度差不符合要求，要进行旋转调节平衡。旋转的本质是通过降低较高子树的一层高度而使左右高度差回到插入前的平衡状态，这样相当于parent子树高度不变，不会影响祖先，所以旋转后不需要再向上更新，可以直接结束。

【4】在【2】的情况不断向上更新直到根，根为+-1就结束了，为+-2则要旋转。

【2】【3】情况结合。

更新到根。 

更新到中间位置结束。 

旋转 

旋转既要保持原来的结构，还要降低被旋树的高度。

但到底要怎么旋？还需分具体情况而论，共有四种情况：左/右单旋，左右/右左双旋。

插入后需要旋转的位置总共就4个，先分出两种大情况：要么在左子树，要么在右子树。

最后就可分为左子树的左，左子树的右，右子树的左，右子树的右。

看起来好像是笔者在自嗨，这总结的情况有点太抽象了。下面用图来展示。

当然这还是抽象图，但至少能够直观看出4种情况了。（如若还是看不清，可以假设只有两个结点，把子树abc当作空结点来看）

具体怎么操作？君且安坐，听笔者慢慢道来。 

右单旋

右单旋本质是以parent为根的右树往下压一层。

右单旋一共就三步，先以10为parent，5为subL，先把subL的右孩子subLR给parent的左，

                                再让parent作为subL的右孩子，

                                最后调整subL与parent->parent的关系。

本例较为简单，parent为根，根的父亲为空，调整步骤简单未在图中显示。

上述步骤在写代码时仍有许多细节问题，请读者自行探索。

左单旋

左单旋本质是以parent为根的左树往下压一层。

左单旋一共就三步，先以10为parent，5为subR，先把subR的右孩子subRL给parent的左，

                                再让parent作为subR的右孩子，

                                最后调整subR与parent->parent的关系。

本例较为简单，parent为根，根的父亲为空，调整步骤简单未在图中显示。

上述步骤在写代码时仍有许多细节问题，请读者自行探索。

左右双旋

双旋的本质是把subLR推举成根，让subL和parent分别做其左右孩子，然后自己的孩子也分别交给他们。（这里的subLR是8）

步骤：先左单旋subL，再右单旋parent。

无论新结点插入在e或f，最终e或f都要交给别人的，不影响旋转逻辑。

右左双旋

与左右双旋同理，

先右单旋subR，再左单旋parent

实现 

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;template<class K, class V>
struct AVLTree_Node
{typedef AVLTree_Node<K, V> Node;pair<K, V> _kv;Node* _left;Node* _right;Node* _parent;int _bf;AVLTree_Node(const pair<K, V> kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTree_Node<K, V> Node;public:bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = cur;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 (kv.first < parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else if (kv.first > parent->_kv.first){parent->_right = cur;cur->_parent = parent;}parent = cur->_parent;while (parent){if (parent->_left == cur)parent->_bf--;else if (parent->_right == cur)parent->_bf++;if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);return true;}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);return true;}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);return true;}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);return true;}}else{assert(false);}}return true;}bool find(const K& k){Node* cur = _root;while (cur){if (k < cur->_kv.first){cur = cur->_left;}else if (k > cur->_kv.first){cur = cur->_right;}else{return true;}}return false;}void Inorder(){_inorder(_root);}int Height(){return _Height(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}
private: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 (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;} if(root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;} // pRoot的左和右如果都是AVL树，则该树⼀定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}void _inorder(Node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->_kv.first<<" ";_inorder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int left_height = _Height(root->_left);int right_height = _Height(root->_right);return left_height > right_height ? left_height + 1 : right_height + 1;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;Node* pp = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pp == nullptr){_root = subL;subL->_parent = nullptr;}else{if (pp->_left == parent){pp->_left = subL;}else if (pp->_right == parent){pp->_right = subL;}subL->_parent = pp;}parent->_bf = subL->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;Node* pp = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pp == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pp->_left == parent){pp->_left = subR;}else if (pp->_right == parent){pp->_right = subR;}subR->_parent = pp;}parent->_bf = subR->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_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(subR);RotateL(parent);if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else 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{assert(false);}}
private:Node* _root = nullptr;
};

红黑树

红黑树是一棵更抽象一点的二叉搜索树，它既没有AVL树那么直观，平衡也不如AVL树那么完美，可是我们使用的map、set等容器底层都是用红黑树实现的。

这就很奇怪了，接下来便让我们一探究竟。

定义

红黑树是一棵空树或是一颗满足以下原则的二叉搜索树：

【1】结点不是红色就是黑色

【2】根节点必须为黑色

【3】红色结点的孩子必须是黑色结点或空，即红色不能连续

【4】从任意结点出发，到达其所有NULL结点的简单路径上，黑色结点数量相同

性质

上面的条件决定了红黑树的性质：

【1】最长路径的长度 <= 最短路径的长度的2倍

先根据[原则4]极端假设，最短路径有bh个黑色结点

再根据[原则2][原则3]可知，红色不能连续，极端场景下，最长路径由一黑一红间隔构成,那么最长路径上的结点个数就为2*bh

最后综合所有原则，理论上最短路径皆为黑色，最长路径一黑一红，不是每棵树都能有的极端情况。假设任意路径上的结点个数为x，则bh <= x <= 2*bh

（假设极端情况）

【2】插入时只能插入红色结点

假设插入的是黑色，那么根据[原则4]，任意结点出发到其所有null的路径上，黑色结点数量相同。在某一支单独插入结点，会影响到各支上的黑色结点个数相等的情况，难以调整。

而反之插入红色结点，不违反[原则4]，但可能违反[原则3]红色结点不能连续。但此时，并不会影响到其他支，只需要在本支上调整颜色即可。

为了不大动干戈，调整所有分支，因此不能插入黑色结点，只能插入影响规模小，易于调整的红色结点。而且若在黑色结点下插入，符合任一原则，不需要进行任何调整，也能提高效率。

【3】效率

已知最长路径<=最短路径的2倍，那么如果N为结点总个数，最短路径的高度为h，最长路径的高度为2*h，则满足2^h - 1 <= N <= 2^2h - 1。可推出 h = logN，最坏情况走最长路径也只为2*logN,所以时间复杂度还是O(logN)。

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，但二者效率仍在同⼀档次，相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。而旋转次数少了就使得效率上优于AVL树，多往下走几层并不会显著影响其效率。所以，也就回答了刚开始的疑问，set、map当然是用更高效的红黑树实现了。
 

结构

结点需要新增一个记录颜色的成员，可以用枚举来实现。

详情见实现。

插入

红黑树虽然因规则多，看起来抽象，但理解之后会发现，其插入确实比AVL树方便。

一共就分为两大种情况，红插黑，红插红。（只插入红色结点，上文有解释）

红插黑是最简单的情况，无需任何处理。

红插红就稍微麻烦点，但大体也只有三种情况。不过在了解这三种情况之前，还需要知道一件事情，——此时，插入的结点记作child, 被插入的记作parent，那么已知child、parent都为红，可以知道parent->_parent即grandparent必为黑（或空）因为插入前树完好，应符合原则。既然child，parent，grandparent的颜色都是确定的，现在唯一的未知量就是uncle了（grandparent的另一个孩子）。

uncle分为不存在，存在黑色，存在红色三种情况。（实际上uncle不存在和存在且为黑是可以合并的一种情况。）

【1】uncle存在且为红：变色

将p和u由红变黑，g变红。这样既能确保红黑相间，又能保持两分支黑色结点数相同。

但有个问题是，g变红后，g的parent也为红（原g为黑），这样又红红连续了，因此还要继续向上变色，直到g的parent为黑或是为根结点时停下。

注意这里插在p的左右是无所谓的。

【2】uncle不存在或存在且为黑：变色+旋转（旋转的转法和AVL树的转法是一致的，可以直接copy。）

（1）变色+单旋

在p外侧插入（只显示了p的新孩子，若有另一个孩子必为黑，按单旋规则给g没问题）

调整方法：单旋g，p变黑，g变红，结束调整。

 （2）变色+双旋

在p的内侧插入就要双旋，把c推举成根，并把c变黑，g变红，就结束调整了。

总结一下，就这两种大情况，理解后其实是要比AVL树还更好理解的（滑稽） 

实现

#pragma once
#include<iostream>using namespace std;enum Color{Red,Black
};template<class K,class V>
struct RBTree_Node
{typedef RBTree_Node Node;RBTree_Node(const pair<K,V>& kv):_kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr),_col(Red){}pair<K, V> _kv;Node* _parent;Node* _left;Node* _right;Color _col;
};//---------------------------------------------------------------------------------------template<class K,class V>
class RBTree
{typedef RBTree_Node<K,V> Node;public:bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = Black;return true;}Node* cur = _root;Node* parent = cur;while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}Node* node = new Node(kv);node->_col = Red;if (kv.first < parent->_kv.first){parent->_left = node;}else{parent->_right = node;}node->_parent = parent;while (parent && parent->_col == Red){Node* grandparent = parent->_parent;if (parent && parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_col == Red){parent->_col = uncle->_col = Black;if(grandparent!=_root)grandparent->_col = Red;cur = grandparent;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == Black){if (cur == parent->_left){RotateR(grandparent);parent->_col = Black;grandparent->_col = Red;}else if (cur == parent->_right){RotateL(parent);RotateR(grandparent);cur->_col = Black;grandparent->_col = Red;}else{return false;}break;}}else if (parent && parent == grandparent->_right){Node* uncle = grandparent->_left;if (uncle && uncle->_col == Red){parent->_col = uncle->_col = Black;grandparent->_col = Red;cur = grandparent;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == Black){if (cur == parent->_right){RotateL(grandparent);parent->_col = Black;grandparent->_col = Red;}else if (cur == parent->_left){RotateR(parent);RotateL(grandparent);cur->_col = Black;grandparent->_col = Red;}else{return false;}break;}}else{return false;}}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_kv.first){cur = cur->_left;}else if (key > cur->_kv.first){cur = cur->_right;}else{return true;}}return false;}void Inorder(){_Inorder(_root);}int Height(){return _Height(_root);}bool isRBTree(){if (_root == nullptr){return true;}if (_root->_col == Red){return Red;}int refBN = 0;Node* cur = _root;while (cur){if (cur->_col == Black){refBN++;}cur = cur->_left;}return check(_root, 0, refBN);}
private:bool check(Node* root, int curBN, int refBN){if (root == nullptr){if (curBN != refBN){cout << "存在路径黑结点数异常" << endl;return false;}return true;}if (root->_col == Red && root->_parent && root->_parent->_col == Red){cout << root->_kv.first << "存在连续红结点" << endl;return false;}if (root->_col == Black)curBN++;return check(root->_left, curBN, refBN)&& check(root->_right, curBN, refBN);}int _Height(Node* root){if (root == nullptr)return 0;int lh = _Height(root->_left);int rh = _Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.second<<" ";_Inorder(root->_right);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pp = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pp == nullptr){_root = subL;subL->_parent = nullptr;}else{if (pp->_left == parent){pp->_left = subL;}else if (pp->_right == parent){pp->_right = subL;}subL->_parent = pp;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pp = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pp == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pp->_left == parent){pp->_left = subR;}else if (pp->_right == parent){pp->_right = subR;}subR->_parent = pp;}}private:Node* _root = nullptr;
};

总结 

AVL树比较直观，红黑树比较抽象。但二者都是能够被理解的。

重点在于不断去模拟二者不同的控制平衡的逻辑，当然也考察了二叉树的知识。

二者都涉及了旋转，怎么旋是好理解的，可实现代码时还有诸多细节，算是很好的锻炼。

不要求手撕，但其本质还是要熟悉的。

（附：未涉及删除操作，有兴趣可以参考相关数据结构教材）