程序员的内功心法-234树

直面弱点，奋发图强！！！

引言

红黑树、B树、B+树，都是软件开发中一个比较难理解和掌握的知识点。他们的本质依然是平衡二叉搜索树。如果直接去学习红黑树、B树、B+树的知识点，无异于雾里看花。这次我们从这些数据结构的底层逻辑设计出发，不牵扯任何代码层面上的内容。

二三四树

定义

• 二节点
  • 一个key和左右两个链接；其中key大于左链接、小于右链接
• 三节点
  • 包含两个key和三个链接（两个key分别称为key1和key2，key1小于key2）
  • 1、2、3三个子链接（子链接1的key小于根结点key1、子链接2的key大于根结点key1且小于根结点key2、子链接3的key大于根结点key2）
• 四节点
  • 包含三个key和四个子链接（三个key分别为key1、key2、key3且从小到大排列）
  • 1、2、3、4三个子链接（子链接1的key小于根结点key1、子链接2的key大于根结点key1且小于根结点key2、子链接3的key大于根结点key2且小于根结点key3、子链接4的key大于根结点key3）
• 上述的节点计数指子链接的数量，而非节点包含的key的数量

操作

由于2、3、4树的查询操作和二叉搜索树的操作一致，不再赘叙。本次主要完成插入和删除的操作描述

可以参考之前的文章，熟悉二叉树一些基本定义和操作

二叉搜索树（BST）

平衡二叉树（AVL）

插入

我们把1-10的数字拆入到一棵234树中

依次插入1、2、3节点

插入4节点，需要将4节点分裂成3个2节点的操作

至此，插入逻辑介绍完毕

删除

节点的删除逻辑，和二叉树的删除逻辑区别不大。如果是叶子节点，可以直接删除；如果是非叶子节点，需要转换为后继/前驱节点的删除方式，所有都可以转换为极值的删除

非2节点的删除

2节点的删删除

对于2节点的删除，需要转换为3、4节点中节点的删除

父节点为非2节点，兄弟节点是2节点

父节点是非2节点，兄弟节点是非2节点

父节点是2节点，兄弟节点非2节点

父节点是2节点，兄弟节点也是2节点

至此，我们的234树的插入和删除操作介绍完了。搞清楚234树的插入和删除操作将是后续红黑树、B树、B+树的前置条件。