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