6.3 删除的叶子节点为 2- 节点
当删除的叶子节点是 2- 节点,则将节点删除后,需要对树进行调整,调整规则如下:
1)当前节点的父节点是 2- 节点,兄弟节点不为 2- 节点,则将兄弟节点的一个 key 上移成父节点,而父节点下移成子节点,此时树满足 2-3-4 树,完成调整。
(2)当前节点的父节点是 2-节点,兄弟节点也为 2- 节点,则此时将父节点与兄弟节点合并,将合并后的节点看成当前节点,然后重复的判断,即判断合并后的当前节点的兄弟节点与父节点的情况,然后走对应的(1)(2)(3)处理,直到满足 2-3-4 树,完成调整。
(3)当前节点的父节点不为 2- 节点,即此时有两个或三个兄弟节点,此时需要根据相邻兄弟节点情形进行调整,规则如下:
(3)-a:若当前节点的相邻兄弟节点为非 3 个 key ,则父节点的一个 key 下移,与相邻兄弟节点合并,此时树满足2-3树,完成调整。
(3)-b:若当前节点的相邻兄弟节点为 3 个 key ,则父节点的一个 key 下移成 1 个 key 的节点,相邻兄弟节点的一个 key 上移与父节点合并,此时树满足 2-3-4 树,完成调整。
图解:
图解: