定义
一棵2-3查找树或为一棵空树,或由以下节点组成:
2-节点:含有一个键和两条链接,左链接指向的2-3树中的键都小于该节点,右链接指向的2-3树中的键都大于该节点.
3-节点:含有两个键和三条链接,左链接指向的2-3树中的键都小于该节点,中链接指向的2-3树中的键都位于该节点的两个键之间,右链接指向的2-3树中的键都大于该节点.
2-3_1.jpeg
一棵完美平衡的2-3查找树中的所有空链接到根节点的距离都应该是相同的.
插入
由于2-3树也是属于二叉查找树中的一种,往树里面插入一个新节点时,肯定是插入到某个叶子节点上.需要分情况讨论因为有两种节点类型.
叶子节点是2-节点: 直接把新节点加入到2-节点生成一个新的3-节点.
2-3_2.jpeg
叶子节点是3-节点:当把新节点加入到3-节点会变成临时的4-节点,然后再进行分解成3个2-节点.
2-3_3.jpeg
把中间的2-节点传递给父亲节点,至于父亲节点是2-节点或者3-节点就可以进行递归处理.直接上图会比较好理解.
2-3_4.jpeg
再看一张图
2-3_5.jpeg
总结
参考算法4.
