《数据结构和算法》——多路查找树
2-3 树：2-3树的节点可以储存两个或三个数据，但是必须保证的是，左侧的数据总比右侧的小，即一个数据左子树的数据总比其小，右子树的数据则相反。我们会使所有的叶子都在同一层，当增加数据时，可以将二节点变为三节点，从而尽可能的提高空间的利用率，当数据超过该深度可存储的数据个数时（即大部分都为三节点时），我们就将三节点拆成二节点，增加树的深度
删除2-3树中的元素是创建的逆过程，我们需要保证所有叶子在同一层，所有当删除的节点在一个三节点中时，我们只需要将三节点变为二节点；当删除的节点在一个二节点叶子上，我们从该节点的兄弟开始向根节点遍历，找到一个三节点，把他拆成两个二节点替代原来节点的位置；当2-3树是一个满二叉树的状态时，我们则将2-3树变成深度减1的新2-3树，来保证每个叶子在同一层
B树：一个m阶的多路查找树
1）若根节点不是叶子，则其至少有两个子树
2）若每一个节点都具有k-1个元素和k个孩子，其中k满足：<=k<=m
3）所以叶子节点都位于同一层
4）每个节点都包涵关键字Ki和指向孩子节点的指针Ai
页:
[1]