一.AVL树（平衡二叉树）

1.1 AVL树的概念

1.2 AVL树的插入

1.3 AVL树插入的实现

1.4 AVL树的旋转

1.5 AVL树的性能

二.红黑树

2.1 红黑树的概念

2.2 红黑树的性质

2.3 红黑树结构

2.4 红黑树的插入操作

2.5 红黑树插入的代码实现

2.6 红黑树的改造

2.7 红黑树的迭代器

2.8 红黑树与AVL树的比较

一.AVL树（平衡二叉树）

1.1 AVL树的概念

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右
子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均
搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN) ，搜索时间复杂度O( logN)。

1.2 AVL树的插入

AVL树节点的定义

template<class K, class V>
struct AVLTreeNode{AVLTreeNode<K, V>* _left;//左节点AVLTreeNode<K, V>* _right;//右节点AVLTreeNode<K, V>* _parent;//双亲节点pair<K, V> _kv;//所存的内容int _bf;//平衡因子//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}};

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

1.3 AVL树插入的实现

template<class K, class V>
struct AVLTreeNode{AVLTreeNode<K, V>* _left;//左节点AVLTreeNode<K, V>* _right;//右节点AVLTreeNode<K, V>* _parent;//父亲节点pair<K, V> _kv;//存的值int _bf;//平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}};template<class K, class V>struct AVLTree{typedef AVLTreeNode<K, V> Node;public://插入bool Insert(const pair<K, V> kv){if (_root == nullptr){_root = new Node(kv);return _root;}Node* parent = nullptr;Node* cur = _root;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;}}cur = new Node(kv);if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else if (cur->_kv.first > parent->_kv.first){parent->_right = cur;}cur->_parent = parent;//控制平衡//1.更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}//当_bf等于0说明插入后对高度没有影响，就跳出循环if (parent->_bf == 0){break;}//当_bf为1或者-1时向上调整平衡因子else if (abs(parent->_bf) == 1){	parent = parent->_parent;cur = cur->_parent;}//说明parent所在子树已经不平衡了，需要旋转处理else if (abs(parent->_bf) == 2){//父亲节点的平衡因子为2，当前节点的平衡因子为1，左旋转if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}//父亲节点的平衡因子为-2，当前节点的平衡因子为-1，右旋转else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//父亲节点的平衡因子为-2，当前节点的平衡因子为1，先左旋，再右旋else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//父亲节点的平衡因子为2，当前节点的平衡因子为-1，先右旋，后左旋else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}private://判断AVL树的平衡因子是不是正常的bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHT = _Height(root->_left);int rightHT = _Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf){cout << root->_kv.first << "的平衡因子异常" << endl;return false;}return  abs(diff) < 2&&_IsBalance(root->_left) && _IsBalance(root->_right);}//找AVL树的高度int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right))+1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//将父亲节点的右节点指向兄弟节点的左节点parent->_right = subRL;if (subRL){//如果兄弟节点的左节点不为空，将他的双亲节点指向父亲节点subRL->_parent = parent;}//祖父节点Node* ppNode = parent->_parent;//将兄弟节点的左节点指向父节点，并将父亲节点的双亲节点指向兄弟节点subR->_left = parent;parent->_parent = subR;//当parent节点是根节点时，让兄弟节点作为新的根节点if (_root == parent){_root = subR;subR->_parent = nullptr;}//parent节点不为根节点时向上继续调整else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}//更新平衡因子subR->_bf = parent->_bf = 0;}//右旋void RotateR(Node* parent){Node* ppNode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}//将兄弟节点的右节点指向父节点，并将父亲节点的双亲节点指向兄弟节点subL->_right = parent;parent->_parent = subL;//当parent节点是根节点时，让兄弟节点作为新的根节点if (_root == parent){_root = subL;subL->_parent = nullptr;}else{//处理旋转的树可能是一个树的子树if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;}//双旋：先左旋后右旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subR = subL->_right;int bf = subR->_bf;RotateL(parent->_left);RotateR(parent);//修改平衡因子subR->_bf = 0;if (bf == 0){parent->_bf = 0;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subL->_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);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}private:Node* _root = nullptr;};

1.4 AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，
使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1. 新节点插入较高左子树的左侧---左左：右单旋

2. 新节点插入较高右子树的右侧---右右：左单旋

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

1.5 AVL树的性能

VL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

二.红黑树

2.1 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

2.2 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

2.3 红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了
与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft
域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下

2.4 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2，针对每种情况进行相应的处理即可。

2.5 红黑树插入的代码实现

enum Colour
{RED,BLACK
};
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(BLACK){}
};
template<class K, class V >
struct RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V> kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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;}}cur = new Node(kv);cur->_col = RED;if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else //(cur->_kv.first > parent->_kv.first){parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//看parent的兄弟节点if (grandfather->_left == parent){Node* uncle = grandfather->_right;//情况1：parent的颜色为红，uncle存在且颜色为红//将parent与uncle的颜色变为黑，grandfather的颜色变红//继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况2与3：uncle不存在 + uncle存在且颜色为黑else{//情况2：右单旋 + 变色//    g//  p   u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情况2：左单旋 + 右单旋 + 变色//    g//  p   u//	 cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else //(grandfather->_right == parent){Node* uncle = grandfather->_left;//情况1：parent的颜色为红，uncle存在且颜色为红//将parent与uncle的颜色变为黑，grandfather的颜色变红//继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况2与3：uncle不存在 + uncle存在且颜色为黑else{//情况2：左单旋 + 变色//    g//  u   p//		  cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情况2：右单旋 + 左单旋 + 变色//    g//  p   u//	 cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return  true;}if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}//PrevCheck(_root, 0);// 黑色节点数量基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return PrevCheck(_root, 0, benchmark);}
private://对红黑树路径判断是否每条路径黑色节点数量相同bool PrevCheck(Node* root, int blackNum, int benchmark){if (root == nullptr){if (blackNum != benchmark){cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}//右旋void RotateR(Node* parent){Node* ppNode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}
private:Node* _root = nullptr;
};

2.6 红黑树的改造

红黑树的应用之一就是用来作为map和set的底层，但是对map和set来说 map要用来存储2个数据，set只需要存储1个内容，那么红黑树要怎么满足2个需求呢，就需要对红黑树进行改造

// 因为关联式容器中存储的是<key, value>的键值对，因此
// k为key的类型，
// ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k
// KeyOfValue: 通过value来获取key的一个仿函数类enum Colour
{RED,BLACK
};
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data){}
};template<class K, class T,class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T , T& , T*> iterator ;iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}pair<iterator,bool> Insert(const T& data){KeyOfT kot;if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(data) < kot(parent->_data)){parent->_left = cur;}else {parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//看parent的兄弟节点if (grandfather->_left == parent){Node* uncle = grandfather->_right;assert(grandfather);assert(grandfather->_col == BLACK);//情况1：parent的颜色为红，uncle存在且颜色为红//将parent与uncle的颜色变为黑，grandfather的颜色变红//继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况2与3：uncle不存在 + uncle存在且颜色为黑else{//情况2：右单旋 + 变色//    g//  p   u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情况2：左单旋 + 右单旋 + 变色//    g//  p   u//	 cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else //(grandfather->_right == parent){Node* uncle = grandfather->_left;//情况1：parent的颜色为红，uncle存在且颜色为红//将parent与uncle的颜色变为黑，grandfather的颜色变红//继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况2与3：uncle不存在 + uncle存在且颜色为黑else{//情况2：左单旋 + 变色//    g//  u   p//		  cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情况2：右单旋 + 左单旋 + 变色//    g//  p   u//	 cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair( iterator(newnode) , true);}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return  true;}if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}//PrevCheck(_root, 0);// 黑色节点数量基准值int benchmark = 0;/*Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}*/return PrevCheck(_root, 0, benchmark);}
private:bool PrevCheck(Node* root, int blackNum, int benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}//右旋void RotateR(Node* parent){Node* ppNode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}private:Node* _root = nullptr;
};

2.7 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代
器，需要考虑以前问题：

begin()与end()：STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s)const{return _node != s._node;}bool operator==(const Self& s)const{return _node == s._node;}//前置++Self& operator++(){if (_node->_right){//下一个就是右子树的最左节点Node* left = _node->_right;while(left->_left){left = left->_left;}_node = left;}else{//找祖先里面孩子不是祖先的右的那个Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_right) {cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}//前置--Self& operator--(){if (_node->_left){//下一个是左子树的最右节点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{//孩子不是父亲的左的那个祖先Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}};