1.红黑树

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或B

lack。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路

径会比其他路径长出俩倍，因而是接近平衡的。

2.红黑树的性质

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

#include <iostream>
using namespace std;enum Colour
{BLACK,RED,
};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(RED){}
};

• 初始颜色给红还是黑?

给红 红可能只会让这一条路线有问题 但给黑 可能造成多条路线有问题 所以给红的危害小

一点 最好给红

3.红黑树的插入

插入情况:

1.空树 插入结点做根 把他变黑

2.插入红结点 父亲黑 结束

3.插入红结点 父亲红 可以推断他的祖父存在且一定为黑色 关键看叔叔

a.如果叔叔存在且为红 把父亲和叔叔变黑 祖父变红 继续往上处理

b.如果叔叔存在且为黑 或者不存在 旋转(单旋 or 双旋)+变色

 折线双旋 直线单旋 旋完后再看变色情况 保证每条支路黑色结点数量一样

cur为当前结点 p为父亲结点 u为叔叔结点 g为祖父结点

pair<Node*, bool> Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK; //根结点必须是黑色return make_pair(_root, true); //插入成功}//二叉搜索树Node* cur = _root;Node* parent = nullptr;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 make_pair(cur, false);}}//将结点插入cur = new Node(kv);Node* newnode = cur;if (kv.first < parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else {parent->_right = cur;cur->_parent = parent;}//------------------------//新增结点红的 or 黑的//破坏b还是c 破坏b较轻 //1.只影响一条路径//2.还不一定破坏规则//所以选红的cur->_col = RED;//-------------------------------//调色//第一种情况:cur为红 p为红 g为黑 只要u存在且为红-> p和u变黑 g变红 继续往上处理 如果到根 根要变回黑 //ps:需要注意的是 这里只关注颜色 而p g u几个结点在左边或者右边是一样的//最后就是为了防止连续的红和保持每条支路黑的结点数量一样//-------------------------------------//第二种情况:cur为红 p为红 g为黑 u不存在/u为黑 直线//1.如果u不存在 那么cur就是新增结点//旋转+变色//旋转:左单旋 or 右单旋//变色:g变红 p变黑//--------------------------------------- //2.如果u存在且为黑 那么cur一定不是新增//你要保证每条路黑色结点数量一样->cur一定是黑的//cur变红的话就是第一种情况//---------------------------------------//第三种情况:cur为红 p为红 g为黑 u不存在/u为黑 折线//旋转:左右双旋 or 右左双旋//变色:g变红 cur变黑//-------------------------------------//parent为红while (parent && parent->_col == RED){Node* grandfather = parent->_parent; if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateR(grandfather); grandfather->_col = RED;parent->_col = BLACK;}else //cur == parent->_right{RotateLR(grandfather); grandfather->_col = RED;cur->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}else //parent是grandfather的右孩子{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateRL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}else //cur == parent->_right{RotateL(grandfather); grandfather->_col = RED;parent->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}}_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）return make_pair(newnode, true);
}//左单旋
void RotateL(Node* parent)
{//需要处理subR的parent left//需要处理subRL的parent//需要处理parent的right parentNode* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}
}//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}
}//左右双旋
void RotateLR(Node* parent)
{RotateL(parent->_left);RotateR(parent);
}//右左双旋
void RotateRL(Node* parent)
{RotateR(parent->_right);RotateL(parent);
}

4.遍历+查找+检验

//中序遍历
void Inorder()
{_Inorder(_root);
}void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);
}//判断是否为红黑树
bool ISRBTree()
{if (_root == nullptr) //空树是红黑树{return true;}if (_root->_col == RED){cout << "error：根结点为红色" << endl;return false;}//找最左路径作为黑色结点数目的参考值Node* cur = _root;int BlackCount = 0;while (cur){if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}int count = 0;return _ISRBTree(_root, count, BlackCount);
}bool _ISRBTree(Node* root, int count, int BlackCount)
{if (root == nullptr) //该路径已经走完了{if (count != BlackCount){cout << "error：黑色结点的数目不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "error：存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){count++;}return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);
}//查找函数
Node* 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 cur; }}return nullptr; 
}

#include "RBTree0.h"int main()
{TestRBTree();return 0;
}

5.AVLTree VS RBTree

#include "AVLTree.h"
#include "RBTree0.h"
#include <vector>
#include <time.h>void TestRB_AVLTree()
{const int n = 100000;vector<int> v;v.reserve(n);srand(time(0));for (size_t i = 0; i < n; ++i){v.push_back(rand());}RBTree<int, int> rbtree;AVLTree<int, int> avltree;size_t begin1 = clock();for (auto e : v){rbtree.Insert(make_pair(e,e));}size_t end1 = clock();size_t begin2 = clock();for (auto e : v){avltree.Insert(make_pair(e, e));}size_t end2 = clock();cout << "rbtree:" << end1 - begin1 << endl;cout << "avltree:" << end2 - begin2 << endl;
}int main()
{TestRB_AVLTree();return 0;
}

【C++】16.红黑树 完