红黑树简介

忘是亡心i 2022-08-26 12:28 7阅读 0赞

一、红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种。二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。这种低效产生的原因是树没有维持一定的平衡性，要提高搜索效率，就要想办法来维持树左边的平衡，也就是要尽时降低树的高度，可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构，使之满足一定的平衡条件。其中一种满足一定平衡条件而且目前应用广泛的是红黑树。它可以在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。而红黑树的查找方法与二叉搜索树完全一样，也能够在O(log N)时间上完成。而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。

红黑树的每个节点上的属性除了有一个key、3个指针：parent、left、right以外，还多了一个属性：color。它只能是两种颜色：红或黑,当然也可以再加一些以key来索引的数据。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下5点性质：

1. 每个节点是黑色的或是红色的。

2. 根节点是黑色的。

3. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点left、right都不指向NULL，而是指向一个定义好的空节点,这样可以保持算法的一致性，简化算法）。

4. 红色节点的父、左子、右子节点都是黑色。

5. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。

如下图就是一棵红黑树：

![红黑树的介绍和实现\[原创\] - saturnman - 一路][- saturnman -]

小记：

1.  在一棵红黑树中null节点是很多的，如果每个null节点都用一个真的节点的话那就太浪费空间了，我们可以对所有的null节点都使用同一个节点，这样可以简化算法又能节约空间。

2.  由于红黑树的结构比较复杂，代码的书写一定要常规，比如一般null的left,right和parent都指向树的根节点，但是一般不应该用null节点来索引根节点或是做相应的判断，因为在一些地方我们为了保持算法的一致性，可能改变null节点的left,right,parent的指向。

3.  这里的红黑树实现并不是真的想拿来应用，而是拿来练习，因此在代码的实现上没有过份的考虑效率而影响可读性，因为红黑树结构复杂，里面很多部分的代码并不能随意写出而无错误，直接写出易引入很多细小的bug,因此很多地方要用数学方法来严格证明算法的正确性。