红黑树前置2-3树

https://www.jianshu.com/p/08024d26c152

定义

一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的定义（父节点的值大于左子树，但小于右子树），所有叶子节点都在同一层。ps：父子节点不能同时为3节点，3节点优先与2个父子单独节点；

合并节点的原则：优先层高减小的策略

(这里合并2，5能减小层高，而合并2,3就不能)

形态

查找

从根节点开始比较，若相等，则结束。如果小于根节点，则说明它应该在左边，选定左节点进行比较；如果大于根节点，则说明在右边，选定右节点进行比较，如不相等，则继续循环。如到最后访问到空节点，则说明没找到。

插入

插入节点后，如果不满足2-3树的性质需要向上合并节点，直到根节点； 如果根节点仍然不满足，需要高度+1得到一个新的根节点

删除

兄弟节点分裂，删除之后简单调整一下父子节点

更复杂的删除调整

删除非叶子节点