23树实现
type
status
date
slug
summary
tags
category
icon
password
这几天在看HashMap中的红黑树，发现较为复杂，就从2-3树开始完整实现了一遍。
为啥会有2-3树
最合理的情况下，是有一棵满二叉树。但是构造一棵满二叉树并不容易。看一下二叉树的一般生长过程
- 二叉树在生长过程中，无法保持总是满的（我给你两个数，你给我弄个满二叉树
- 生长一般是自顶向下的，左右子树的树高容易不一致（极端情况下，退化成链表
如果第2步，不急着分清父子，第3步才来生成一棵2-Tree的话，就能得到一棵满树。
同样的推广到4，5步，再重新变形一下
emmm，这好像不是一棵满树啊。因为依旧是向下生长，并没有改变其左右不均匀的问题。那我们试着往上试试。
看起来除了A有两个爸爸，其他好像没啥问题啊。依然满足节点左侧所有点小于节点，右侧所有点大于节点。稍微变形一下
一棵满的3-Tree闪亮登场。
生成2-3树
插入
对于2-3树的每个叶子节点来说，只有两种情况
- 空2-Tree变成空3-Tree
- 空3-Tree变成满2-Tree
升级
当叶子节点由空3-Tree变为满2-Tree的时候，我们选择往上生长，这个过程就叫它升级好了。也只有两种情况
- 满2-Tree的子结点由空3-Tree变成满2-Tree，整个满2-Tree变成满3-Tree
- 满3-Tree的子结点由空3-Tree变成满2-Tree，整个满3-Tree变成满4-Tree，再分解成满两棵满2-Tree，树高+1
伪代码实现
首先定义树
然后就是插入代码
上面的伪代码简化了将子树插入到父结点中的过程（分左边，中间，和右边插入的情况
删除
删除要相对复杂一点，我们先简化问题，删除某个叶子结点，就以删除最小值为例。分两种情况
- 是一个空的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，树高也被调整了，不过，由于是根结点调整，所以没有影响。
删除非叶子结点
这个其实也很简单
- 找到最接近它的叶子结点（左树的最右叶子，右树的最左叶子）。
- 将它的值改为叶子结点的值。
- 删掉叶子结点
代码实现
Loading...