其每一个节点的孩子数，可以多于两个，且每一个节点可以存储多个元素
2-3树
其中的每一节点都具有两个孩子（称为2结点）或者3个孩子（称为3结点）
一个2结点包含一个元素和两个孩子（或没有孩子）
一个3节点包含一大一小两个元素和三个孩子（或没有孩子）
2-3树中所有的叶子结点都在同一层次上。
插入
情况1：对于空树，插入2结点即可。
情况2：插入结点到一个2结点的叶子上。由于本身只有一个元素，只需要将其升级为3结点即可
情况3：向3节点中插入一个新元素。因为3结点本身已经是2-3树的结点的最大容量（已经有两个元素），因此就需要将其拆分，且将树中两个元素或插入元素的三者中选择其一向上移动一层。
删除
情况1：所删除元素位于一个3结点的叶子结点上，只需要在该节点处删除该元素即可。
情况2：所删除的元素在一个2节点上，即要删除的是一个只有一个元素的结点。
情况3：所删除的元素位于非叶子的分支结点。此时我们通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可。
B树
B树是一种平衡的多路查找树，2-3树是B树的特例。结点最大的孩子数目称为B树的阶。2-3树是3阶B树。
1.如果根节点不是叶结点，则至少有两棵子树。
2.每一个非根的分支节点都有k-1个元素和k个孩子(m/2<=k<=m)。
3.所有叶子结点在同一层次
网友评论