首页 > 技术文章 > 算法导论笔记——第十八章 B树

justinh 2017-08-22 16:42 原文

18.1 B树的定义

 18.2 B树的基本操作

与一棵二叉搜索树一样,可以在从树根到叶子这个单程向下过程中将一个新的关键字插入B树中。为了做到这一点,当沿着树向下查找新的关键字所属位置时,就分裂沿途遇到的每个满结点(包括叶节点本身)。如分裂一个满的根,首先要让根成为一个新的空根结点的孩子。树的高度因此增加1,分裂是树长高的唯一途径。

18.3 从B树中删除关键字

我们设计的这个过程必须保证无论何时,结点x递归调用自身时,x中关键字个数至少为最小度数t。使得有时在递归下降至子结点之前,需要把一个关键字移到子结点中。

 

推荐阅读