11.2.B树

\(11.2\)\(B\)

1.\(B\)树的引入

  导致\(BST\)最坏运行时间的原因是:每次insert操作,我们都选择在叶子上进行,这导致了树的高度的增加。因此,一个自然的想法是:能否在不增加树的高度的前提下插入节点。

  为了达到这个目的,我们可以在一个叶子中插入多个节点,这样就不会导致叶子高度的增加了。

  但如果无限制地在一个叶子中插入,那么这个叶子就会退化成一个链表了。因此,我们可以对单个叶子能够装入节点的数量设置限度(\(limit\)),例如\(4\)。当叶子中节点个数超过\(4\)个时,就通过弹出中间的节点,把这个叶子分开(\(split\))。

2.\(2-3\)搜索树

  一棵\(2-3\)搜索树是满足如下条件的树:

  • 空的(\(empty\))。
  • 一个叶子存储一个节点,同时有两个链接(\(link\)),和\(BST\)类似。
  • 一个叶子存储二个节点,同时有三个链接。设二个节点分别为\(x,y\),则三个链接所指向的其它叶子分别满足\(a_i\leq x,x\leq a_i\leq y,a_i\leq y\)

3.查找流程

  \(2-3\)搜索树查找节点的流程如下:

4.插入流程

  \(2-3\)搜索树插入节点的流程如下:

  1. 我们仍然一直在左叶子进行插入操作。
  2. 将节点插入对应的叶子时,如果该叶子的节点个数大于\(3\),则弹出中间靠左的节点(如果是奇数个节点就直接弹出中间的),然后相应地重新排列子树。
  3. 重复上述步骤,直到找到一个有空位的父节点或者遍历到根节点。

  一些插入情况对应的图示如下:

  分开叶子的图示如下: