java实现常见查找算法(8)

在 B 树上查找的过程是一个指针查找结点和在结点中查找关键字的交叉过程。

比方说，我们要查找数字7，首先从外存(比如硬盘中)读取得到根结点3、5 、8三个元素，发现7不在当中，但在5和 8之间，因此就通过A2再读取外存的6、7结点，查找到所要的元素.

至于 B 树的插入和删除，方式是与2-3树和2-3-4树相类似的，只不过阶数会很大而已 。

我们在本节的开头提到，如果内存与外存交换数据次数频繁，会造成了时间效率

上的瓶颈，那么B树结构怎么就可以做到减少次数呢?

我们的外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说， 一页的长度可能是211到214个字节。

在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对B树进行调整，使得 B树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001(即1个结点包含1000个关键字) ，高度为2，它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。这就好比我们普通人数钱都是一张一张的数，而银行职员数钱则是五张、十张 ，甚至几十张一数，速度当然是比常人快了不少。

通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。

二分查找算法是在有序数组中用到的较为频繁的一种算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为o(n).但二分查找算法则更优，因为其查找时间为o(lgn)，譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：。此时，使用先二分查找，后顺序遍历的算法，二分查找只能使用一次，顺序遍历199次，最终对比了200次。昨天看了一下关于树中的面试题，发现二叉树中的面试题比较常见的题型大概有下面几个：创建一颗二叉树（先序，中序，后序）、遍历一颗二叉树（先序，中序，后序和层次遍历）、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值。

可是在B树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问，如下图所示，我们希望遍历这棵B树，假设每个结点都属于硬盘的不同页面，我们为了中序遍历所有的元素，页面2→页面1→页面 3→页面1→页面4→页面1→页面5。而且我们每次经过结点遍历时，都会对结点中的元素进行一次遍历，这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢?

为了能够解决所有元素遍历等基本问题，我们在原有的B树结构基础上，加上了新的元素组织方式，这就是B+树。

我认为只要删除某个结点的指针就可以删除这个元素，比如我在做后序遍历时，为了避免结点间重复进行，就在输出某个叶子结点时一并将其删除，但是我只是free（q）而没有将其双亲节点的指针指向null，这样那个叶子结点是删除不了的。1．在具有 n 个叶子结点的严格二叉树中，结点总数为（ ） a．2n+1 b．2n c．2n-1 2．除根结点外，树上每个结点（ ） a．可有任意多个孩子、任意多个双亲 b．可有任意多个孩子、一个双亲 c．可有一个孩子、任意多个双亲 d．只有一个孩子、一个双亲 3．具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。是b+树的变体，在b+树的非根和非叶子结点再增加指向兄弟的指针。

例如下图所示，就是一棵B+树的示意，灰色关键字即是根结点中的关键字

在叶子结点再次列出，并且所有叶子结点都链接在一起。

一棵m阶的B+树和m阶的B树的差异在于:

• 有n棵子树的结点中包含有n个关键字;

⑵所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且。所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)。每个t结点都包含一系列从小到大排序后的元素和 三个指针，指针分别指向父结点和左右结点。

• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大(或最)关键字。

这样的数据结构最大的好处就在子 ，如果是要随机查找，我们就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。

如果我们是需要从最小关键字进行从小到大的顺序查找，我们就可以从最左侧的叶子结点出发，不经过分支结点c 二叉排序树，而是延着指向下一叶子的指针就可遍历所有的关键字。

按序号查找结点值在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域null。是b+树的变体，在b+树的非根和非叶子结点再增加指向兄弟的指针。否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。

B+树的插入、删除过程也都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已。

引用《大话数据结构》作者：程杰

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-106859-8.html