红黑树并没有我们想象的那么难(上) - 捣乱小子 - 博客园

红黑树并没有我们想象的那么难(上) - 捣乱小子 - 博客园

<红黑树并没有我们想象的那么难> 上、下两篇已经完成, 希望能帮助到大家.

• 红黑树并没有我们想象的那么难(上): http://daoluan.net/blog/?p=2057
• 红黑树并没有我们想象的那么难(下): http://daoluan.net/blog/?p=2112

红黑树并没有想象的那么难, 初学者觉得晦涩难读可能是因为情况太多. 红黑树的情况可以通过归结, 通过合并来得到更少的情况, 如此可以加深对红黑树的理解. 网络上的大部分红黑树的讲解因为没有「合并」. 红黑树的五个性质:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。

Read full article from 红黑树并没有我们想象的那么难(上) - 捣乱小子 - 博客园