2-3 Tree
2-3 树是一种二叉查找树的推广, 来提供更好的执行效果
结点
结点类型 | 键数目 | 孩子数目 |
---|---|---|
2 结点 | 1 | 2 |
3 结点 | 2 | 3 |
2 结点图示
3 结点图示
graph TD 1(B D)---| 小于 B|2(A) 1---| 介于 B 和 D 之间 | 4(C) 1---| 大于 B|3(E)
RULE
完美平衡 | 每条从根节点到空链接的路径有相同的长度 |
---|---|
对称顺序 | 中序遍历得到升序序列 |
检索
从一个 2-3 树中检索 H
graph TD 1(M)---|<1> H 小于 M|2(E J) 1---3(R) 2---4(A C) 2---|<2> H 介于 E 和 J 之间 OK|5(H) 2---0(L) 3---8(P) 3---9(S X)
插入
插入键落在底部 2 结点上
往一个 2-3 树中插入 K
检索 K
graph TD 1(M)---|<1> K 小于 M|2(E J) 1---3(R) 2---4(A C) 2---5(H) 2---|<2> K 大于 J|0(L) 3---8(P) 3---9(S X)
将 2 结点变为 3 结点
graph TD 1(M)---2(E J) 1---3(R) 2---4(A C) 2---5(H) 2---0(K L) 3---8(P) 3---9(S X)
插入键落在底部 3 结点上
往一个 2-3 树中插入 Z
检索 K
graph TD 1(M)---2(E J) 1---|<1> Z 大于 M|3(R) 2---4(A C) 2---5(H) 2---0(L) 3---8(P) 3---|<2> Z 大于 R|9(S X)
- graph TD 1(A E S)
- (将 4 结点换为两个二节点, 同时将中间的键传递给父结点)
- graph TD 1(E)---2(A) 1---3(S)
- graph TD 1(E)---2(A C D) 1---3(S)
- graph TD 1(C E)---2(A) 1---4(D) 1---3(S)
- graph TD 1(C E)---2(A) 1---4(D) 1---3(S T U)
- graph TD 1(C E T)---2(A) 1---4(D) 1---3(S) 1---5(U)
- graph TD 8(E)---1 8---7(T) 1(C)---2(A) 1---4(D) 7---3(S) 7---5(U)
来源: http://www.bubuko.com/infodetail-3142225.html