一、红黑树的概念及性质

1.1 红黑树的概念

AVL树用平衡因子让树达到高度平衡

红黑树可以认为是AVL树的改良

通过给每个节点标记颜色让树接近平衡

以减少树在插入节点的旋转

在每个结点新增一个存储位表示结点颜色

可以是Red或Black

通过对任何一条从根到叶子的路径上

各个结点着色方式的限制

红黑树确保没有一条路径会比其他路径长出

俩倍，因而是接近平衡的

1.2 红黑树的性质

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的

则它的两个孩子结点是黑色的对于每个结点

从该结点到其所有后代叶结点的简单路径上

均包含相同数目的黑色结点每个叶子结点都是黑色的

(此处的叶子结点指的是空结点)

为啥满足上面性质的红黑树就能保证

其最长路径节点个数不会超过最短路径

节点个数的两倍？

由性质3可得出不能出现连续红色节点

由性质4可得出每条路径有相同黑色节点数量

极限情况下

最短路径：全黑

最长路径：一黑一红

由此可得出

最长路径不会超过最短路径的两倍

1.3 为什么更常用红黑树而不是AVL树？

AVL树： 是一颗高度平衡的二叉树

查找效率：

O

(

l

o

g

N

)

O(logN)

O(logN)

但是这样的效率是在插入元素时

经常性的旋转换来的

红黑树： 是一颗接近平衡的二叉树

假设全部黑节点有N个

整棵树的节点数量：[N, 2N]之间

最短路径长度：

O

(

l

o

g

N

)

O(logN)

O(logN)

最长路径长度：

O

(

2

l

o

g

N

)

O(2logN)

O(2logN)

查找效率：

O

(

2

l

o

g

N

)

O(2logN)

O(2logN)

10亿数据AVL树最多查找30次

红黑树最多也就查找60次

对于cpu的运行速度来说几乎可以忽略不计

但红黑树的规则相对于AVL树没那么严格

在插入元素时，不会经常旋转

所以综合而言红黑树更胜一筹

如图： 对于AVL树必定旋转

红黑树则不用

二、红黑树模拟实现的基本框架

2.1 红黑树节点的定义

跟AVL树一样

只是AVL树采用平衡因子

让树达到平衡

而红黑树对节点进行颜色标记

让树达到平衡

定义一个枚举表示节点颜色

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(RED)

{ }

};

template <class K, class V>

class RBTree

{

typedef RBTreeNode<K, V> Node;

public:

private:

Node* _root = nullptr;

};

2.2 红黑树的插入

还是和AVL树一样

bool Insert(const pair<K, V>& kv)

{

if (_root == nullptr)

{

_root = new Node(kv);

return true;

}

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

if (cur->_kv.first < kv.first) // 插入节点比当前节点大往右走, 小往左走

{

parent = cur;

cur = cur->_right;

}

else if (cur->_kv.first > kv.first)

{

parent = cur;

cur = cur->_left;

}

else

{

return false;

}

}

// 链接

cur = new Node(kv);

if (parent->_kv.first > kv.first)

{

parent->_left = cur;

}

else

{

parent->_right = cur;

}

// new的节点的parent还指向空

cur->_parent = parent;

// 插入黑色节点还是红色节点？

return true;

}

插入走到这里如果是AVL树

此时需要更新平衡因子

红黑树采用的是标记节点颜色

让树达到平衡

需要考虑的是插入什么颜色的节点？

插入黑色节点

会违反规则4，影响到每条路径插入红色节点

如果插入节点的父节点也是红色节点

则会违反规则3影响当前局部节点

很明显插入红色节点更划算

所有插入的节点都默认是红色

如果违反红黑树的规则，再进行调整

三、对插入节点调整的解析

如果插入节点的父节点为黑

则无需处理

如果为红，则分为三种情况

情况一：

cur为红，p为红，g为黑，u存在且为红

cur为当前节点，p为父节点

g为祖父节点，u为叔叔节点

把p和u变黑，g变红

如果grandfather的parent也为红

把grandfather改为cur

继续按刚才的步骤往后迭代

如果grandfather为根节点

把grandfather改为黑色

颜色调整结束

情况二：

cur为红，p为红，g为黑

u不存在或u存在且为黑

此树可能是完整树也可能是子树

u节点不存在

p为g的左孩子，cur为p的左孩子

则进行右单旋转

相反

p为g的右孩子，cur为p的右孩子

则进行左单旋转

p、g变色–p变黑，g变红

下图则是u节点存在的情况

c为下面4种情况的

任意一种包含一个黑节点的红黑树

d和e可能是空或者一个红节点

插入新节点，更新完后

继续往后更新

就是情况二的u存在的情况

情况三：

cur为红，p为红，g为黑

u不存在或u存在且为黑

跟情况二完全类似

只是情况三为双旋

情况二是单旋

p为g的左孩子，cur为p的右孩子

则针对p做左单旋转

相反

p为g的右孩子，cur为p的左孩子

则针对p做右单旋转

则转换成了情况2

此图为u不存在

u存在参考情况二

四、红黑树插入代码的全部实现

详解都在代码注释

各位友友们请耐心看完

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 (cur->_kv.first < kv.first) // 插入节点比当前节点大往右走, 小往左走

{

parent = cur;

cur = cur->_right;

}

else if (cur->_kv.first > kv.first)

{

parent = cur;

cur = cur->_left;

}

else

{

return false;

}

}

// 链接

cur = new Node(kv);

if (parent->_kv.first > kv.first)

{

parent->_left = cur;

}

else

{

parent->_right = cur;

}

// new的节点的parent还指向空

cur->_parent = parent;

// 如果新插入节点破坏了红黑树规则

// 则更新节点颜色

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

if (grandfather->_left == parent)

{

Node* uncle = grandfather->_right;

// 情况1：u存在且为红，变色处理，并继续往上处理

if (uncle && uncle->_col == RED)

{

parent->_col = BLACK;

uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上调整

cur = grandfather;

parent = cur->_parent;

}

else // 情况2+3：u不存在或者u存在且为黑，旋转+处理

{

// 如果插入节点在父节点的左，c、p、g呈一条斜线

// g

// p u

// c

if (parent->_left == cur)

{

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// 插入节点在父节点的右，c、p、g呈一条折线

// g

// p u

// c

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

// parent->_col = RED; // 父亲本就是红，变一下双重保险

grandfather->_col = RED;

}

break;

}

}

else // (grandfather->_right == parent)

{

Node* uncle = grandfather->_left;

// 情况1：u存在且为红，变色处理，并继续往上处理

if (uncle && uncle->_col == RED)

{

parent->_col = BLACK;

uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上调整

cur = grandfather;

parent = cur->_parent;

}

else // 情况2+3：u不存在或者u存在且为黑，旋转+处理

{

// g

// u p

// c

if (parent->_right == cur)

{

RotateL(grandfather);

grandfather->_col = RED;

parent->_col = BLACK;

}

else

{

// g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

_root->_col = BLACK; // 做个双保险，无论那种情况把根都变成黑的

return true;

}

五、红黑树全部代码模拟实现

gitee链接

✨✨✨✨✨✨✨✨

本篇博客完，感谢阅读🌹

如有错误之处可评论指出

博主会耐心听取每条意见

✨✨✨✨✨✨✨✨