红黑树
1. 基于 2-3 Tree
为了让树高能够维持~lg(n)。
保持各个底部空链接和root距离相等(为了维持这个性质，后面插入时才会有各种变化)
1.1 结构
- 2节点(含有一个key和两个链接)
- 3节点(含有两个key和三个链接)
1.2 操作
- 2节点 插入-->直接添加，变成3节点
- 3节点 插入-->直接添加，然后裂变成三个2节点
- 向父节点为2节点的 3节点 插入-->父节点变3节点，然后下面裂变成2个2节点
- 向父节点为3节点的 3节点 插入-->会一直向上裂变，知道遇到2节点
2. 红黑树就是2-3树的一个实现
1.1 结构
- 2节点(含有一个key和两个链接) ，就是普通链接，我们叫这种链接为黑链接
- 3节点(含有两个key和三个链接)，为了在二叉树中模拟出这种节点，我们设计两个节点由左斜链接相连的为3节点，其中的链接叫红链接
由此产生两个性质(联想2-3树原型就可以看出):
- 红链接均为左链接
- 没有任何一个节点与两个红链接相连
- 树是黑色平衡的。
如何表示红键：我们在每个node设一个color，其指代指向这个节点的链接的颜色。
网友评论