red-black tree.png
算法导论中的红黑树
- 每个节点或者是红色的，或者是黑色的
- 跟节点是黑色的
- 每一个叶子节点（最后的空节点）是黑色的
- 如果一个节点是红色的，那么他的孩子节点都是黑色的
- 从任意一个节点到叶子节点，经过的黑色节点是一样的
算法4中的红黑树
红黑树与2-3树的等价性
2-3树
满足二分搜索树的基本性质
节点亦可以存放一个或者两个元素
每个节点有两个孩子或三个孩子
nodes.png
对于a节点，左孩子小于a，右孩子大于a
对于bc节点，左孩子小于b，b<中间孩子<c，右孩子>c
2-3 tree example.png
2-3树是绝对平衡的树（根节点到任意一个叶子节点所经过的节点数量是相同的）
