定义
在查找操作中,经常会用到二叉查找树,其最好的性能是O(logN),但是,由于输入的不同,所以一个查找二叉树会有各种不同的高度,最坏会导致查找退化到O(N),所以我们要想构造一种,无论输入是什么,都可以确保其运行时间是对数级别的二叉查找树
二叉树的内容可以参考
sheng的学习笔记-二叉树（BST）_coldstarry的博客-CSDN博客
为了要保证树的平衡性,我们做出了一些妥协,允许一个节点有多个键.在2-3树中,一个节点最多可以有两个键,三个链接.每一个链接都对应其中保存的键所分割出来的一个区间.比如说我们有一个节点,键为 10 20 , 那么三个链接的区间就是x=20.其严格的定义如下
一颗完美平衡的2-3查找树中,所有叶子节点到根节点的距离都是相同的
查找节点
我们首先来看一下这样的树是怎么进行查找的.根据定义,我们知道2-3树的每个节点要么有2个键,要么有一个键,当我们开始查找时,首先会与根节点的值进行比较,根据大小来确定往左节点还是右节点向下比较,当只有一个键时,比较过程与一般的二叉查找树一样,当有两个键的时候,会对这两个键进行两次比较以确定查找节点的区间,然后再根据对应的链接查找下一层的节点.如图所示
插入节点
向2-节点中插入
要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用2-3树的主要原因就在于它能够在插入之后继续保持平衡。
如果未命中的查找结束于一个2-结点，我们只要把这个2-结点替换为一个3-结点，将要插入的键保存在其中即可
向只有3-节点的树插入
如果有一个3-节点没有父节点,我们要向其插入新的节点时,会比上面的情况复杂一点.由于这个节点已经有两个键了,所以没有给其拓展的空间,我们可以为了方便,先将其插入到这个节点,使其变成一个4-节点.创建这个节点的原因是,4-节点很容易可以变成3个2-节点,中间的键作为两边的键的父节点即可.这样整个树的高度就会增加
向父节点为2-节点的3-节点的树插入
如果我们想要插入的话,可以先将当前节点变为一个4-节点,然后将其中心键上移,使父节点变成了一个3-节点,左键为父节点的中间链接,右键为父节点的右链接
向父节点为3-节点的3-节点的树插入
遇到这种情况无疑是最复杂的了,无论是当前节点还是父节点,都已经没有了拓展的空间.所以我们只好从父节点的根节点继续向上找,直到遇到树的根节点或者一个2-结点为止.并且我们向上一层,就要重新对键的排布以及链接的指向进行重新排列.如果树的根节点是2-节点,并且之前都没有2-节点,那么我们最终会将键放入根节点,使其成为一个3-节点
如果树的根节点是一个3-节点,那么我们最终会将这个键放到根节点处,让根节点成为一个临时的4-节点,并使其生长,整个树的高度加一
分解4-节点
在2-3树中,最复杂的变换莫过于将临时的4-节点分解为2-节点和3-节点了.我们知道,将一个4-节点分解为2-3树可能会有6种情况,分别是当其为根节点,2-节点的左右节点和3-节点的左中右节点的时候.好在的是,分解4-节点是一种局部的操作,其分解不会影响全局树的结构.即不会影响树的全局有序和完美平衡性.如图所示,分解4-节点一般来说,就是向其父节点插值
当完成变换之后,并不会影响树的高度(根节点变换除外)
局部变化的六种情况
构造归集
2-3树的弊端
优点
跟标准的二叉树由上往下生长不同，2-3树的生长是由下向上。在最坏的情况下还是有很好的性能
缺点
2-3树其实相对于一般的二叉查找树来说,已经有了巨大的提升,但是他的弊端就是实现起来太不方便了,我们要定义多种节点的数据类型,对不同节点还有不同的操作方式,在节点的分解与节点的扩增的时候,数据类型转换带来的开销也不容小觑.所以对于平衡查找树来说,更多的会用到红黑树而不是2-3查找树.
参考文章：
书：算法