二叉排序树，AVL树，B树（多路查找树）,B+树

程序员文章站 2022-05-18 16:55:39

...

一.二叉排序树

1.定义：对于一颗二叉树，它的左子树若不为空，则左子树上所有结点的值小于它的根结点的值，若右子树不为空，则右子树上的所有结点的值大于它的根结点的值。且它的左右子树也分别为二叉排序树。
2.总结：

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作上不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除性能比较好。
- 对于二叉排序树的查找，走的是根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况下，最少为1次，即根结点就是要查找的结点，最多也不会超过树的深度。也就是说二叉排序树的查找性能取决于二叉排序树的形状。
- 对于，{35,37,47,51,58,62,73,88,93,99}所构成的二叉排序树就称为了一颗极端的右斜树，但它任是一颗二叉排序树。此时需要引入AVL树的概念。

    每个结点的孩子数可以多余两个，且每个结点可以存储多个元素。

1.2-3树：（最简单的B树）
- 2结点包含一个元素和两个孩子（或没有孩子）。
- 3结点包含两个元素和三个孩子（或没有孩子）。
- 并且2-3树的所有叶子结点都在同一层上。

2.-3-4树
同上
4结点包含3个元素和4个孩子（或没有孩子）；

3.B树

结点最大的孩子书称为B树的阶。2-3树是3阶B树，2-3-4树是4阶B树。
如果结点不是叶结点，则其至少有两颗子树。
每一个非根的分支结点都有k-1个元素和k个孩子，其中⌈m/2⌉<=k<=m。
各一个叶子结点n都有n-1个元素，其中⌈m/2⌉<=k<=m。
所有叶子结点都位于同意层次。
所有结点包含以下信息数据（n,A0,K1,A1,K2,A2….,Kn,An）,其中，K1…Kn为关键字，且K1 < Kn；A0.。。。An为指向子树根节点的指针，且指针Ai-1所指子树中所有关键字均要小于Ki，An所指子树中的关键字均要大于Kn。
总结
在B树上查找过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。
由于B树每个结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为了内外存的数据交互准备的。
例子：比如说一个B树的阶树为1001（即1个结点包含1000个关键字），高度为2。那么它可以存储超过10亿个关键字。我们只要将根结点持久的保留在内存中，那么在这棵树上，寻找一个关键字至多需要读取两次硬盘即可。

4.B+树
提出原因：对于B数，遍历时，会多次对根节点进行遍历，造成损耗。

B树中每个元素只会在该树中出现一次，有可能在叶子结点，也有可能在分支结点。而在B+树中，出现在分子结点中的元素会被当作他们在该分支结点位置的中序后继者（叶子结点）中再次出现。另外，每个叶子结点都会保存一个指向后一个叶子结点的指针。
所以，B+树中所有的叶子结点包含了全部的关键字信息，及指向包含这些关键字记录的指针，叶子结点本身依照关键字大小自小而大顺序排列。
所有分支结点可以看成索引，结点中仅含有其子树中的最大（最小）关键字。
B+树结构特别适合带有范围的查找，比如说查找年龄19-22岁的学生人数，可以通过从根结点出发找到第一个19岁的学生，再在叶子结点中按照顺序查找到符合范围的所有记录。