一、基本概念

红黑树（red-black tree） 是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

红黑树具有以下性质：

  • 每个结点或是红色的，或是黑色的。
  • 根结点是黑色的。
  • 每个叶结点(NIL)是黑色的。
  • 如果一个结点是红色的，则它的两个子结点都是黑色的。
  • 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

一颗典型的红黑树如下图所示（其中的NIL可以理解为空指针）：

1618913549400.png

一棵有 n 个内部结点的红黑树的高度至多为$2log_2(n+1)$。关于该结论的证明，可以参阅《算法导论》中的相关证明，这里不再进行赘述。

二、旋转

指针结构的修改是通过旋转（rotation）来完成的，这是一种能保持二叉搜索树性质的搜索树局部操作。下图给出了两种旋转：左旋和右旋。

1618915142702.png

下面来简单介绍一下左旋和右旋是如何实现的：

1、左旋

1618915836461.png

2、右旋

1618916198071.png

三、插入

这里先挖个坑，有时间再回来填，这里先推荐几个介绍红黑树的文章和视频：

https://zhuanlan.zhihu.com/p/79980618

https://zhuanlan.zhihu.com/p/91960960

https://www.bilibili.com/video/BV1iJ411E7xW?p=124

四、删除

这里先挖个坑，有时间再回来填。