rb-tree

rb-tree

早就听说红黑树的大名,不过还没有实现过,这次趁着数据结构的课设要实现set,就实现一下红黑树。

定义和性质

红黑树是一种自平衡的二叉树,查找,删除,插入的时间复杂度都是log(n).
下面是红黑树需要满足的要求:
1.节点是红色或黑色。
2.根是黑色。 
3.所有叶子都是黑色(叶子是NIL节点)。 
4.每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)  
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

为什么红黑树是近平衡的

我们可以从上面的定义通过不是很严禁的推理,或者说是我自己的理解推出一些结论。首先我们这样想,只看最后的一条,因为对任何的节点都需要使其不论走哪一条路,到叶子节点所以经过的黑色的节点的数量是一样的,所以我们先假设,这棵树是全黑的,那么按照性质描述的,这棵树应该是一个满的二叉树,也就是有2^n-1个节点的那种,并且对任何的节点,它的的左右子树一定是对称的,这个由节点全黑和第五条性质就可以很明显的看出。接下来我们要做的就是向里面添加红色的节点,并且尽可能破坏这棵树的平衡,这里的平衡可以理解为这棵树的左右子树的高度差,也就是我们要使这两课树的高度差最大,那么我们就要只在其中一边加入红的节点(这里以左边为例,右边一样),另一边不变,但是根据4,红色的两个子节点必须是黑的,所以我们只能在左子树隔一行插入一行红色,那么最后左边的高度就是右边的两倍了,并且左边已经不能再高了。经过上面不严谨的推理,我们就可以说,红黑树是一个左右子树中高那一个不会比矮的哪一个高出一倍的树。虽然相对于AVL的相差不超过二要宽一些,但是在时间复杂度的数量级上是不差的。

实现

这个,网上已经有很多人实现了,就不细写了,有想看实现的可以去看我的github.  

拓展

其实当我们弄懂了红黑树的原理之后,我们可以很简单的模仿红黑树的定义实现一个长的一部分的子树的高度小于等于短的树的3倍的4倍的等等很多的类似红黑树的树。其实关于红黑树的最重要的是它的两个性质,首先是关于红的子孩子必须是黑,另一个是第五条,保证路上的黑色是相等的。