【揭秘红黑树：高效数据结构解析】

---

前言

`
红黑树是在二叉搜索树的基础上多出一些变化规则，以此让左右子树趋近平衡。

注意：
红黑树是趋近平衡，AVL树才是平衡；
AVL和红黑树不论底层实现还是功能都基本上一致。

---

一、红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。 通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

(一)红黑树的规则

1. 每个结点不是红⾊就是⿊⾊   
2. 根结点是⿊⾊的    
3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点。   
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点 

说明：《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是⿊⾊的规则。他这⾥所指的叶⼦结点不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道⼀下这个概念即可。

(二)红黑树最长路径与最短路径

• 由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为bh(black height)。
• 由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为2*bh。
• 综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2 * bh。

(三)红黑树的效率

假设N是红⿊树树中结点数量，h最短路径的⻓度，那么2^ h − 1 <= N < 2 ^（2∗h） − 1 , 由此推出 h ≈ logN ，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 2 ∗ logN ，那么时间复杂度还是 O(logN).
红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

二、红黑树的实现

红黑树的主要接口有插入、删除、查找、遍历。
其中，红黑树的删除、查找、遍历代码实现几乎和二叉树搜索树一致，故不再重复说明，可以参考[二叉搜索树]。(https://blog.csdn.net/2501_90956005/article/details/150230291?spm=1001.2014.3001.5501)

而红黑树的实现中最复杂的就是红黑树的插入，重点理解！

(一) 红黑树的结构

/ 枚举值表⽰颜⾊
enum Colour
{RED,BLACK
};
// 这⾥我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{// 这⾥更新控制平衡也要加⼊parent指针pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col=RED;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://红黑树的常用接口实现//......private:Node* _root = nullptr;
};

(二) 红黑树的插入

首先，红黑树的插入要分为以下进行讨论：
说明：下图中假设我们把新增结点标识为c (cur)，c的⽗亲节点标识为p(parent)，p的⽗亲节点标识为g(grandfather)，p的兄弟节点标识为u（uncle）
情况一：u存在且为红
情况二：u不存在或者是⿊⾊的，且插入节点靠近树的边缘，如图一。
情况三：u不存在或者是⿊⾊的，且插入节点靠近树的内部，如图二。

图一：

图二：

1.情况一

u存在且为红

这是三种情况中最简单的情况。
处理：c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红。在把g当做新的c，继续往上更新。
图示：

2.情况二

u不存在或者是⿊⾊的，且插入节点靠近树的边缘

这种情况我们仍然像情况一样进行处理，就会破坏红黑树的结构规则，所以这里需要像AVL树一样进行旋转处理。

旋转分为向左旋、向右旋转。
下面是我画的抽象图：
其中，g为旋转函数传入参数，圈起来的内容表示关系无变化，连线内容表示关系出现变化。

代码示例：
注：旋转结束后要更新节点颜色。

//向右旋转
void Rotate_R(Node*& grandparent)
{Node* parent = grandparent->_left;Node* temp = parent->_right;Node* pgrandpaent = grandparent->_parent;grandparent->_left = temp;if (temp)temp->_parent = grandparent;parent->_right = grandparent;grandparent->_parent = parent;if (grandparent == _root){_root = parent;parent->_parent = nullptr;}else{if (pgrandpaent->_left = grandparent){pgrandpaent->_left = parent;parent->_parent = pgrandpaent;}else{pgrandpaent->_right= parent;parent->_parent = pgrandpaent;}}
}
//向左旋转
void Rotate_L(Node*& grandparent)
{Node* parent = grandparent;Node* temp = parent->_left;Node* pgrandparent = grandparent->_parent;grandparent->_right = temp;if (temp)temp->_parent = grandparent;grandparent->_parent = parent;parent->_left = grandparent;if (grandparent == _root){_root = parent;parent->_parent = nullptr;}else{if (pgrandparent->_left = grandparent){pgrandparent->_left = parent;parent->_parent = pgrandparent;}else{pgrandparent->_right = parent;parent->_parent = pgrandparent;}}
}

3.情况三

u不存在或者是⿊⾊的，且插入节点靠近树的内部

这中情况需要复用两次单次旋转来进行处理，且两次旋转必须为先左旋后右旋或者先右旋后左旋。

然后再对节点颜色进行更新。

注：通过观察旋转前后变化图可以知道，节点颜色的更新可以只看结果，而不去注意过程。

4.插入代码示例

void Rotate_R(Node*& grandparent)
{Node* parent = grandparent->_left;Node* temp = parent->_right;Node* pgrandpaent = grandparent->_parent;grandparent->_left = temp;if (temp)temp->_parent = grandparent;parent->_right = grandparent;grandparent->_parent = parent;if (grandparent == _root){_root = parent;parent->_parent = nullptr;}else{if (pgrandpaent->_left = grandparent){pgrandpaent->_left = parent;parent->_parent = pgrandpaent;}else{pgrandpaent->_right= parent;parent->_parent = pgrandpaent;}}
}void Rotate_L(Node*& grandparent)
{Node* parent = grandparent;Node* temp = parent->_left;Node* pgrandparent = grandparent->_parent;grandparent->_right = temp;if (temp)temp->_parent = grandparent;grandparent->_parent = parent;parent->_left = grandparent;if (grandparent == _root){_root = parent;parent->_parent = nullptr;}else{if (pgrandparent->_left = grandparent){pgrandparent->_left = parent;parent->_parent = pgrandparent;}else{pgrandparent->_right = parent;parent->_parent = pgrandparent;}}}bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv.first,kv.second);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > kv.first){parent = cur;cur = cur->_left;}else if (cur->_key < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv.first, kv.second);if (parent->_key>kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while(parent&&parent->_col==RED){	Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_left == cur){Rotate_R(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{Rotate_L(grandparent);Rotate_R(grandparent);grandparent->_col = RED;cur->_col = BLACK;}return true;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_left == cur){Rotate_L(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{Rotate_R(grandparent);Rotate_L(grandparent);grandparent->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return true;
}

(三)红黑树的验证

在进行完红黑树的增删查操作后，我们可能会对红黑树的结果重新验证，判断它还是不是红黑树。
这里仅提供思路：
使用前序遍历，期间如果遍历到红色节点，对该节点的父节点颜色进行判断，如果父节点也为红色，那么他就不是红黑树，返回false；反之继续遍历，直到遍历结束返回true;同时也要对每条路径的黑色节点进行比较，若都为同一个值，则true；反之则为false。

三、红黑树整体代码示例

#pragma once#include<iostream>
#include<string>using namespace std;enum Colour
{RED,BLACK
};template<typename K,typename V>
struct RBNode
{RBNode(const K& key,const V& value):_key(key),_value(value){}K _key;V _value;RBNode<K, V>* _parent=nullptr;RBNode<K, V>* _left=nullptr;RBNode<K, V>* _right=nullptr;Colour _col=RED;
};template<typename K,typename V>
class RBTree
{typedef RBNode<K, V> Node;
public:void Rotate_R(Node*& grandparent){Node* parent = grandparent->_left;Node* temp = parent->_right;Node* pgrandpaent = grandparent->_parent;grandparent->_left = temp;if (temp)temp->_parent = grandparent;parent->_right = grandparent;grandparent->_parent = parent;if (grandparent == _root){_root = parent;parent->_parent = nullptr;}else{if (pgrandpaent->_left = grandparent){pgrandpaent->_left = parent;parent->_parent = pgrandpaent;}else{pgrandpaent->_right= parent;parent->_parent = pgrandpaent;}}}void Rotate_L(Node*& grandparent){Node* parent = grandparent;Node* temp = parent->_left;Node* pgrandparent = grandparent->_parent;grandparent->_right = temp;if (temp)temp->_parent = grandparent;grandparent->_parent = parent;parent->_left = grandparent;if (grandparent == _root){_root = parent;parent->_parent = nullptr;}else{if (pgrandparent->_left = grandparent){pgrandparent->_left = parent;parent->_parent = pgrandparent;}else{pgrandparent->_right = parent;parent->_parent = pgrandparent;}}}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv.first,kv.second);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > kv.first){parent = cur;cur = cur->_left;}else if (cur->_key < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv.first, kv.second);if (parent->_key>kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while(parent&&parent->_col==RED){	Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_left == cur){Rotate_R(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{Rotate_L(grandparent);Rotate_R(grandparent);grandparent->_col = RED;cur->_col = BLACK;}return true;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_left == cur){Rotate_L(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{Rotate_R(grandparent);Rotate_L(grandparent);grandparent->_col = RED;cur->_col = BLACK;}break;}}}return true;}void InOrder(){_InOrder(_root);}Node* Find(const K& key){if (_root == nullptr)return nullptr;Node* cur = _root;while (cur){if (key>cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return cur;}}return nullptr;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " " << root->_value << endl;_InOrder(root->_right);}Node* _root=nullptr;
};

---

总结

红黑树的插入实现是红黑树学习的核心内容，对于插入的代码最好能自行实现一下，且实现过程中最好多画画图。
同时，红黑树也是map/set封装的底层实现，理解红黑树对于学习map/set打下基础。