这几天在看HashMap中的红黑树，发现较为复杂，就从2-3树开始完整实现了一遍。

为啥会有2-3树

最合理的情况下，是有一棵满二叉树。但是构造一棵满二叉树并不容易。看一下二叉树的一般生长过程

绘图

  • 二叉树在生长过程中，无法保持总是满的（我给你两个数，你给我弄个满二叉树
  • 生长一般是自顶向下的，左右子树的树高容易不一致（极端情况下，退化成链表

如果第2步，不急着分清父子，第3步才来生成一棵2-Tree的话，就能得到一棵满树。

二叉树生长过程1-3

同样的推广到4，5步，再重新变形一下

二叉树生长过程4-5

emmm，这好像不是一棵满树啊。因为依旧是向下生长，并没有改变其左右不均匀的问题。那我们试着往上试试。

2-3

看起来除了A有两个爸爸，其他好像没啥问题啊。依然满足节点左侧所有点小于节点，右侧所有点大于节点。稍微变形一下

3-Tree

一棵满的3-Tree闪亮登场。

生成2-3树

插入

对于2-3树的每个叶子节点来说，只有两种情况

  • 空2-Tree变成空3-Tree

插入1

  • 空3-Tree变成满2-Tree

插入2

升级

当叶子节点由空3-Tree变为满2-Tree的时候，我们选择往上生长，这个过程就叫它升级好了。也只有两种情况

  • 满2-Tree的子结点由空3-Tree变成满2-Tree，整个满2-Tree变成满3-Tree

变形1

  • 满3-Tree的子结点由空3-Tree变成满2-Tree，整个满3-Tree变成满4-Tree，再分解成满两棵满2-Tree，树高+1

变形2

伪代码实现

首先定义树

class Tree {
    var p: Tree? = null //父亲
    var v: LinkedList<Int> = LinkedList() //结点值
    var c: LinkedList<Tree> = LinkedList() //子结点
    
    val type
        get() = "${v.size}-${c.size}" //根据值的数量和子结点数量确定树的类型
}

然后就是插入代码

fun insert(tree: Tree) {
    when (tree.type) {
        "1-0" -> {//添加一个单点
            when (this.type) {
                "1-0" ->  this.v.add(tree.v[0])//转变成一个 empty-3-tree即可
                "2-0" -> { //转变成一个新的full-2-tree
                	p?.remove(this)//从父节点移除自己
                	this.from3To2()//将自己变成一棵满2-Tree
                	p?.insert(this)//将自己加入到父结点中
                }
                "1-2", "2-3" -> {
                	val child = this.findChildByValue(tree.v) //找到合适子结点
                	child.insert(tree)//交由子结点处理
                }
                else -> throw RuntimeException()
            }
        }
        "1-2" -> {//添加一个full-2-tree
            this.v.add(tree.v[0])//把值加入
            this.c.addAll(tree.c)//把子结点加入
            when (this.type) {
                "2-3" -> {//full-2-tree（某个子结点进位) -> full-3-tree -> keep
                //do nothing
                }
                "3-4" -> {//full-3-tree（某个子节点进位) -> full-4-tree -> 2 full-2-tree
                    p?.remove(this)//从父节点移除自己
       				this.from4To2()//
                    p?.insert(this)//将自己加入到父结点中
                }
                else -> throw RuntimeException()
            }
        }
        else -> throw RuntimeException()
    }
}

上面的伪代码简化了将子树插入到父结点中的过程（分左边，中间，和右边插入的情况

删除

删除要相对复杂一点，我们先简化问题，删除某个叶子结点，就以删除最小值为例。分两种情况

  • 是一个空的3-Tree，只需将其变成一个空2-Tree就好了。
  • 是一个空的2-Tree

空的2-Tree不能动，因为一旦删除空的2-Tree，左右树高就会不一致，就不满足二三树的条件了。那我们就想办法把其变成一棵3-Tree（懒得画SVG了，here we go

变形

  • 情况2和3本质上是同样的解法

  • 情况4中的在删除完毕后，4-Tree会消失

  • 上面的1，无解，只能先递归把父结点先调整好

其核心在于，不能修改树高。唯一的特例是，当一路调整回溯到根结点的时候，根结点是个2-Tree，且两个子结点都是2-Tree，这个时候我们需要合成一个满的4-Tree，树高也被调整了，不过，由于是根结点调整，所以没有影响。

root

删除非叶子结点

这个其实也很简单

  1. 找到最接近它的叶子结点（左树的最右叶子，右树的最左叶子）。

  2. 将它的值改为叶子结点的值。

  3. 删掉叶子结点

代码实现

Gist