数据结构-红黑树

red-black tree.png

算法导论中的红黑树

1. 每个节点或者是红色的，或者是黑色的
2. 跟节点是黑色的
3. 每一个叶子节点（最后的空节点）是黑色的
4. 如果一个节点是红色的，那么他的孩子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的

算法4中的红黑树

红黑树与2-3树的等价性

2-3树

满足二分搜索树的基本性质
节点亦可以存放一个或者两个元素
每个节点有两个孩子或三个孩子

nodes.png

对于a节点，左孩子小于a，右孩子大于a
对于bc节点，左孩子小于b，b<中间孩子<c，右孩子>c

2-3 tree example.png

2-3树是绝对平衡的树（根节点到任意一个叶子节点所经过的节点数量是相同的）