2-3查找树
特点和性质
一颗2-3查找树或为一颗空树,或由一下结点组成:
- 2-结点,含有一个键(及其对应的值)和两条链,
左链指向2-3树中的小于该结点,
右链接指向的2-3树中的键都大于该结点。
- 3-结点,含有两个键(及其对应的值)和三条链接
左链接指向2-3树中的键都小于该结点,
中链接指向的2-3树中的键都小于该结点的两个键之间,
右链接指向的2-3树中的键都大于该结点
一颗完美的2-3中所有的空连接到根节点的距离都是相同的。
在一颗大小为N的2-3树中,查找和插入操作访问的节点数必然不超过lgN个。
查找
插入
先进行一次未命中的查找,然后把新结点挂在树底部(让树保持平衡)。为了保持树的平衡,需要对插入做一下情况分析
case1:向2节点插入
如果未命中的查找结束于一个2-结点,只需要将2-结点变成一个3-结点
case2:向一颗只含有1个3-结点的书中插入
case3:秀昂一个父节点为3-结点的3结点中插入新键
先插入变成4-结点,再提升(分解)中间结点,层层提升,直到遇到一个2-结点,并将它替换为一个不需要分解的3-结点,或者到达3-结点的根
case4:分解根节点
同理,分解,会将树的高度提升+1