一. 什么是红黑树？
1. 基本概念
红黑树和AVL树类似，是对搜索树的优化。不同于AVL树的绝对平衡，红黑树是近似平衡，即对于每个节点的以它为根的所有路径，其中最长路径的节点数不大于最短路径节点数的2倍。
2. 红黑树的特性
- 每个节点不是红色就是黑色，其中根节点为黑
- 红色节点不连续，即红色节点的左右孩子只能为黑色
- 每个节点，以它为根的所有路径中黑色节点的数量相同
以上特性，就是红黑树近似平衡的原因：
- 红色节点不连续，说明最短路径的节点都是黑色，最长路径的节点是红黑相间。
- 每条路径节的黑色节点个数必须相同，决定了最短路径不超过最长路径的2倍。
二. 为什么要有红黑树？
为什么要有红黑树？下面通过红黑树和搜索树、平衡树的比较来回答这个问题。
1. 红黑树和搜索树
当插入有序数据时，搜索树会退化为单枝树从而导致查找效率降为线性。红黑树通过对各个节点颜色的控制和位置的调整，使得树永远处于近似平衡状态，保证了O(logN)的查找效率。
2. 红黑树和平衡树
二者都是对搜索树进行了平衡处理
- 平衡树是绝对平衡：左右子树高度差的绝对值小于等于1
- 红黑树是近似平衡：最长路径不大于最短路径的2倍
红黑树不追求绝对平衡，相对平衡树而言降低了插入和删除时旋转的次数，频繁的插入删除红黑树的性能更优，并且红黑树的实现也较为简单，所以实际运用中红黑树更多。如果插入删除的操作较少且需要频繁的查找，那么平衡树性能更优。
三. 红黑树插入操作实现
1. 基本框架
主要定义里两个类：节点类 + 树的本体，其中前者存储节点节点的相关信息，后者主要实现红黑树的功能，如插入、删除、查找等。
1.1 节点类框架
数据域：颜色（默认为红）、pair键值对
指针域：左孩子和右孩子、父亲
// 枚举定义颜色 enum COLOR { RED, BLACK }; // 节点的定义 template<class k, class v> struct RBTreeNode { // 构造函数，颜色默认给为红色 RBTreeNode(const pair<k, v>& kv) :_color(RED) ,_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) {} COLOR _color; pair<k, v> _kv; RBTreeNode<k, v>* _parent; RBTreeNode<k, v>* _left; RBTreeNode<k, v>* _right; };
为什么颜色默认为红色？
因为红色处理起来更简单，对其他路径的波及较小。如果为黑色，想想看这条路径的黑色节点数量加了一个，那么其他路径都要调整来保证所有路径的黑色节点个数一致；但是如果置为红色，这时只有插入位置的父亲也为红才需要调整，即使调整也只需调整一条路径，比较容易。
1.2 树本体框架
只有一个成员变量就是一个节点的指针，代表树的根节点。也为只有一个成员变量，可以不用写构造函数，我们直接声明时给缺省值即可，就是把它置为nullptr。
// 树的定义 template<class k, class v> class RBTree { public: typedef RBTreeNode<k, v> Node; private: Node* _root = nullptr;// 声明时给缺省值 };
2. 第一步：按搜索树性质插入节点
按搜索树的性质来找到插入的位置，然后直接插入：
- 如果是空树，则则该插入节点就作为整棵树的根，并把颜色改为黑色
- 非空的话，按照搜索树的性质找到插入的位置和并记录父亲，然后和父亲的key比较来决定作为左孩子还是右孩子。
template<class k, class v> class RBTree { public: typedef RBTreeNode<k, v> Node; bool Insert(const pair<k, v>& kv) { // 第一步：按搜索树规则插入一个节点 // 1、空树的话插入节点作为根节点 // 2、不空的话，按搜索树规则找到插入的位置，然后插入 if(!_root) { _root=new Node(kv); _root->_color=BLACK; return true; } // 寻找插入的位置 Node* parent=nullptr; Node* cur=_root; while(cur) { parent=cur; if(cur->_kv.first == kv.first) { return false; } else if(cur->_kv.first < kv.first) { cur=cur->_right; } else if(cur->_kv.first > kv.first) { cur=cur->_left; } } // 找到后插入 Node* newNode=new Node(kv); newNode->_parent=parent; if(parent->_kv.first > kv.first) { parent->_left=newNode; } else if(parent->_kv.first < kv.first) { parent->_right=newNode; } // 未完待续..... private: Node* _root=nullptr; };
3. 第二步：调整节点的颜色
3.1 调整操作
走到了这一步，那么插入节点肯定不是整棵树的根了，因为空树情况在第一步里面已经处理好了，也就是说现在插入的新节点一定有父亲。根据父亲的颜色分两种情况处理：
- 情况一：父亲颜色为黑。这种情况就不用调整了，插入结束。
- 情况二：父亲颜色为红。需要调整
针对情况二，我们需要知道，这时一定是有祖父节点的，即父亲的父亲一定存在且为黑色，因为父亲的颜色为红不可能是根节点，又因为红色不连续所以祖父为黑。这时我们的调整取决于叔叔，当然叔叔可能存在也可能不存在，我们分情况处理。
约定插入节点为cur，父亲为parent，祖父为gfather，叔叔为uncle，此时：
uncle存在且为红 --》 把parent和uncle的颜色到改为黑，gfather颜色改为红，从gfather开始继续往上调整。
uncle 不存在 or 存在且为黑 --》依照gfather、parent、cur的关系来旋转处理。
// 拼接到第一步代码后面 // 第二步：调整节点的颜色 // 1、如果父亲颜色为黑就不用调整 // 2、如果父亲节点颜色为红，调整方式由叔叔决定 // a、叔叔存在且为红 --> 把叔叔和父亲的颜色调整为黑，爷爷颜色调整为红，然后继续往上调整 // b、叔叔不存在或存在且为黑 --> 看爷爷、父亲、和cur的相对位置来决定用什么旋转，旋转后交换父亲和爷爷的颜色 cur=newNode; while(parent && parent->_color == RED) { // 既然进来了这个循环内部，说明父亲一定是红色，那么一定有爷爷且爷爷颜色为黑 Node* grandfather = parent->_parent; // 确定叔叔的位置 if(grandfather->_left == parent) { Node* uncle=grandfather->_right; if(uncle && uncle->_color == RED)// 叔叔存在且为红 { parent->_color=uncle->_color=BLACK; grandfather->_color=RED; cur=grandfather; parent=cur->_parent; } else // 叔叔不存在或者存在且为黑 { if(cur == parent->_right) { RotateL(parent); std::swap(parent,cur); } RotateR(grandfather); parent->_color=BLACK; grandfather->_color=RED; break; } } else if(grandfather->_right == parent) { Node* uncle=grandfather->_left; if(uncle && uncle->_color==RED)// 叔叔存在且为红 { uncle->_color=parent->_color=BLACK; grandfather->_color=RED; cur=grandfather; parent=cur->_parent; } else // 叔叔不存在或存在且为黑 { if(cur == parent->_left) { RotateR(parent); std::swap(parent,cur); } RotateL(grandfather); parent->_color=BLACK; grandfather->_color=RED; break; } } } _root->_color=BLACK; } // 左单旋 void RotateL(Node* parent) { Node* subR=parent->_right; Node* subRL=subR->_left; parent->_right=subRL; if(subRL != nullptr) { subRL->_parent=parent; } subR->_left=parent; Node* pparent=parent->_parent; parent->_parent=subR; if(pparent == nullptr) { _root=subR; subR->_parent=nullptr; } else { subR->_parent=pparent; if(pparent->_left == parent) { pparent->_left=subR; } else if(pparent->_right == parent) { pparent->_right=subR; } } } // 右单旋 void RotateR(Node* parent) { Node* subL=parent->_left; Node* subLR=subL->_right; parent->_left=subLR; if(subLR != nullptr) { subLR->_parent=parent; } subL->_right=parent; Node* pparent=parent->_parent; parent->_parent=subL; if(pparent == nullptr) { _root=subL; subL->_parent=nullptr; } else { subL->_parent=pparent; if(pparent->_left == parent) { pparent->_left=subL; } else if(pparent->_right == parent) { pparent->_right=subL; } }
3.3 调整总结
4. 完整代码
#pragma once #include <iostream> using std::cin; using std::cout; using std::endl; using std::pair; // 枚举定义颜色 enum COLOR { RED, BLACK }; // 节点的定义 template<class k, class v> struct RBTreeNode { // 构造函数，颜色默认给为红色 RBTreeNode(const pair<k, v>& kv) :_color(RED) ,_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) {} COLOR _color; pair<k, v> _kv; RBTreeNode<k, v>* _parent; RBTreeNode<k, v>* _left; RBTreeNode<k, v>* _right; }; // 树的定义 template<class k, class v> class RBTree { public: typedef RBTreeNode<k, v> Node; // 插入一个节点 bool Insert(const pair<k, v>& kv) { // 第一步：按搜索树规则插入一个节点 // 1、空树的话插入节点作为根节点 // 2、不空的话，按搜索树规则找到插入的位置，然后插入 if(!_root) { _root=new Node(kv); _root->_color=BLACK; return true; } // 寻找插入的位置 Node* parent=nullptr; Node* cur=_root; while(cur) { parent=cur; if(cur->_kv.first == kv.first) { return false; } else if(cur->_kv.first < kv.first) { cur=cur->_right; } else if(cur->_kv.first > kv.first) { cur=cur->_left; } } // 找到后插入 Node* newNode=new Node(kv); newNode->_parent=parent; if(parent->_kv.first > kv.first) { parent->_left=newNode; } else if(parent->_kv.first < kv.first) { parent->_right=newNode; } // 第二步：调整节点的颜色 // 1、如果父亲颜色为黑就不用调整 // 2、如果父亲节点颜色为红，调整方式由叔叔决定 // a、叔叔存在且为红 --> 把叔叔和父亲的颜色调整为黑，爷爷颜色调整为红，然后继续往上调整 // b、叔叔不存在或存在且为黑 --> 看爷爷、父亲、和cur的相对位置来决定用什么旋转，旋转后交换父亲和爷爷的颜色 cur=newNode; while(parent && parent->_color == RED) { // 既然进来了这个循环内部，说明父亲一定是红色，那么一定有爷爷且爷爷颜色为黑 Node* grandfather = parent->_parent; // 确定叔叔的位置 if(grandfather->_left == parent) { Node* uncle=grandfather->_right; if(uncle && uncle->_color == RED)// 叔叔存在且为红 { parent->_color=uncle->_color=BLACK; grandfather->_color=RED; cur=grandfather; parent=cur->_parent; } else // 叔叔不存在或者存在且为黑 { if(cur == parent->_right) { RotateL(parent); std::swap(parent,cur); } RotateR(grandfather); parent->_color=BLACK; grandfather->_color=RED; break; } } else if(grandfather->_right == parent) { Node* uncle=grandfather->_left; if(uncle && uncle->_color==RED)// 叔叔存在且为红 { uncle->_color=parent->_color=BLACK; grandfather->_color=RED; cur=grandfather; parent=cur->_parent; } else // 叔叔不存在或存在且为黑 { if(cur == parent->_left) { RotateR(parent); std::swap(parent,cur); } RotateL(grandfather); parent->_color=BLACK; grandfather->_color=RED; break; } } } _root->_color=BLACK; } private: // 左单旋 void RotateL(Node* parent) { Node* subR=parent->_right; Node* subRL=subR->_left; parent->_right=subRL; if(subRL != nullptr) { subRL->_parent=parent; } subR->_left=parent; Node* pparent=parent->_parent; parent->_parent=subR; if(pparent == nullptr) { _root=subR; subR->_parent=nullptr; } else { subR->_parent=pparent; if(pparent->_left == parent) { pparent->_left=subR; } else if(pparent->_right == parent) { pparent->_right=subR; } } } // 右单旋 void RotateR(Node* parent) { Node* subL=parent->_left; Node* subLR=subL->_right; parent->_left=subLR; if(subLR != nullptr) { subLR->_parent=parent; } subL->_right=parent; Node* pparent=parent->_parent; parent->_parent=subL; if(pparent == nullptr) { _root=subL; subL->_parent=nullptr; } else { subL->_parent=pparent; if(pparent->_left == parent) { pparent->_left=subL; } else if(pparent->_right == parent) { pparent->_right=subL; } } } Node* _root=nullptr; };
