2-3查找树

特点和性质

一颗2-3查找树或为一颗空树，或由一下结点组成：

  • 2-结点，含有一个键（及其对应的值）和两条链，

左链指向2-3树中的小于该结点，
右链接指向的2-3树中的键都大于该结点。

  • 3-结点，含有两个键（及其对应的值）和三条链接

左链接指向2-3树中的键都小于该结点，
中链接指向的2-3树中的键都小于该结点的两个键之间，
右链接指向的2-3树中的键都大于该结点

一颗完美的2-3中所有的空连接到根节点的距离都是相同的。
image.png
在一颗大小为N的2-3树中，查找和插入操作访问的节点数必然不超过lgN个。

查找

看图比较容易理解，这里直接上图
image.png

插入

先进行一次未命中的查找，然后把新结点挂在树底部（让树保持平衡）。为了保持树的平衡，需要对插入做一下情况分析

case1：向2节点插入

如果未命中的查找结束于一个2-结点，只需要将2-结点变成一个3-结点

case2：向一颗只含有1个3-结点的书中插入

先插入变成4-结点，再提升中间结点
image.png

case3：秀昂一个父节点为3-结点的3结点中插入新键

先插入变成4-结点，再提升（分解）中间结点，层层提升，直到遇到一个2-结点，并将它替换为一个不需要分解的3-结点，或者到达3-结点的根
image.png

case4：分解根节点

同理，分解，会将树的高度提升+1
image.png