红黑树学习笔记

摘要

红黑树学习笔记。

在08、09年的时候，那个时候因为工作的需求，需要研究文件系统，然后就遇到了红黑树，也就研究了一下红黑树，不过时至今日，感觉已经记不太清楚了，感觉当时可能也没有研究的很透彻。

最近的工作中，又遇到了红黑树，就捡起来复习复习。孔子说，“温故而知新，可以为师矣”，我为不了师，不过发现，温故确实是可以知新的。

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

想要充分理解红黑树，有一些前提条件，需要充分理解二叉树和平衡二叉树，否则，对于红黑树，是很难充分理解的，所以，红黑树可能先看到这里，先去仔细看看平衡二叉树。