数据结构复习之平衡树2-3查找树（中）

四、平衡树

之前学习过二叉查找树，它的效率高于单纯的链表和数组，
但是在最坏的情况下，二叉查找树的性能仍然糟糕。
例如：9 8 7 6 5 4 3 2 1 插入到树中就会形成类似链表的结构

这样，如果要查找1这个元素时间复杂度就是O(n)，作为改进就使用了2-3查找树

2-3查找树：

我们将一棵标准的二叉树中的结点称为2-结点，现在我们引入3-结点，它包含有两个键和三条链。

• 2-结点：含有一个键（及其对应的值）和两条链，分别指向其左子树和右子树
• 3-结点：含有两个键和三条链，最左边的链指向的结点都小于两个键中最小键，中间的链指向位于两键之间的元素，最右边的键指向大于两个键中最大键的结点

2-3查找树的查找算法：

• 类似二叉查找树，要判断一个键是否在树中，先与根结点比较，如果命中返回
• 若没有命中根据键的大小关系去其左右子树中寻找
• 如果遇到3-结点，如果该键小于3-结点中最小的键直接去左子树，如果大于3-结点中最大的键直接去右子树，否则去中间的链对应的结点
• 如果寻找到空节点则未命中

对H结点的查找：

• H<M，进入左子树3-结点进行比较
• H>E && H<J，进入2-结点H
• H=H，查找命中

2-3查找树的插入算法：

2-3查找树的插入分为多种情况，往2-3查找树中插入元素和往二叉查找树插入元素一样，首先进行查找，然后将结点挂载到没有结点的位置。如果最后查找到的是一个2-结点就非常容易直接将2-结点转换为3-结点即可，但如果最后查找到的是一个3-结点，就比较麻烦。以下逐个分析

1、向2-结点中插入新键

• K<M,去3-结点E-J
• K>J，去2-结点L
• K<L，且L的左子结点为Null
• 将L结点转换为3-结点 K-L
  

2、向一棵只含有一个3-结点的树中插入新键

假设一棵树只有一个3-结点，则它没有空间插入第三个键。那么插入方法为，暂时将其变为4-结点。然后将4-结点的中间结点提升，左边的键作为左子结点，右边的键作为右子结点。之后就变为2-3查找树

• 将A-E结点变为临时4-结点A-E-S
• 将E提升，左子结点为A，右子结点为S

3、向一个父节点为2-结点的3-结点中插入新键

与上面情况类似，将新元素插入3-结点中，形成一个4-结点，之后将结点中间元素提升，与父节点组成3-结点，将其子树连接在适当的链中。

• Z>X，形成4-结点S-X-Z
• 提升X结点，与R形成3-结点
• （tips：敲黑板，因为树是有序的，R的右子树均大于R，X结点提升后S小于X位于左子树，所以当X与R组成3-结点时R<S<X,S可以直接放在3-结点的中间链即可）
• P为最左结点、S为中间结点、Z为最右结点

4、向一个父节点为3-结点的3-结点中插入新键

类似以上步骤，一直套娃，直到遇到一个父节点为2-结点的结点停止

• 将3-结点A-C转变为临时4-结点A-C-D
• 将C提升至结点E-J，再次形成临时4-结点C-E-J
  • 下方挂四个结点从左到右依次为A D H L（原理同上tips）
• 将E结点提升至M，形成3-结点E-M
  • 下方挂两个结点C J
    • C下又挂A D
    • J下挂H L
      

5、分解跟结点

如果跟结点也已经是3-结点，那么插入是就将根3-结点分解称为2-结点，树的深度增加

• A-C结点变为A-C-D临时4-结点
• C提升至E-J结点形成4-结点C-E-J
• 因为C-E-J已经是根结点，所以提升变为2-结点，深度增加
• 提升E，左子节点变为C、右子结点变为 J

2-3查找树的性质：

• 任意空链到根结点的距离相同（因为如果为空就会把X-结点升级为(X+1)-结点）
• 2-3查找树是自底向上生长的树，二叉查找树是自顶向下生长
• 只有当4-结点分裂时树的深度会增加