数据结构中的公用树（BST二进制搜索树，AVL平衡二进制树，RBT红黑树，B树，B

BST树

二进制搜索树:

1. 所有非叶节点最多有两个儿子（左和右）；

2. 所有节点都存储一个关键字；

3. 非叶节点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

例如:

BST树搜索从根节点开始，如果查询关键字等于节点关键字，则命中；

否则，如果查询关键字小于节点关键字，请输入左儿子；如果大于node关键字，请输入

好儿子；如果左儿子或右儿子的指针为空，则找不到相应的关键字；

如果BST树的所有非叶节点的左右子树的数量保持相同（平衡），则B树

的搜索效果

接近二进制搜索；但是它比连续搜索空间中的二进制搜索更有优势，因为它改变了BST树的结构

（插入和删除节点）不需要移动很大部分的内存数据，甚至不需要固定的开销；

例如:

但是，在多次插入和删除之后，BST树可能会导致不同的结构:

右侧也是BST树平衡二叉排序树，但其搜索性能已经是线性的；同一组关键字可能会导致不同的

树结构索引；因此，在使用BST树时，还必须考虑保持BST树结构尽可能远，并避免使用正确的图片结构，即

这是所谓的“平衡”问题；

AVL平衡二进制搜索树

定义: 具有以下属性的平衡二叉树或空树或二叉排序树:

（1）左右子树的深度之差的绝对值不超过1；

（2）左右子树仍然是平衡的二叉树.

平衡因子BF =左子树深度-右子树深度.

平衡二叉树的每个节点的平衡因子只能为1、0，-1. 如果其绝对值超过1，则二进制排序树不平衡.

如图所示是平衡树和不平衡树的:

RBT红黑树

AVL是一棵严格平衡的树，因此在添加或删除节点时，根据不同情况，旋转次数要多于红色和黑色树；

红色和黑色之间的平衡较弱. 添加或删除节点时使用非严格平衡来减少旋转数；

因此，简单来说，搜索数量远大于插入和删除操作，然后选择AVL树. 如果进行搜索，插入和删除的次数几乎相同，则应选择RB树.

红黑树中的每个节点包含五个字段，颜色平衡二叉排序树，键，左，右，p. 如果相应的指针字段不存在，则将其设置为NIL.

通常，红黑树满足以下属性，即只有满足以下所有属性的树才称为红黑树:

1）每个节点都是红色或黑色.

2）根节点是黑色的.

3）每个叶节点，即空节点（NIL）为黑色.

4）如果节点为红色，则其两个儿子均为黑色.

5）对于每个节点，从该节点到其子孙的所有路径都包含相同数量的黑色节点.

下图显示了一棵红黑树:

B树

这是一个平衡的多向搜索树（不是二进制）:

1. 定义任何非叶节点最多有M个儿子；和M> 2;

2. 根节点的子节点数为[2，M];

3. 根节点以外的非叶子节点的数量为[M / 2，M];

4. 每个节点至少存储M / 2-1（取整）和最多M-1个关键字； （至少2个关键字）

5. 非叶节点关键字的数量=指向子代-1的指针的数量；

6. 非叶节点的关键字: K [1]，K [2]，…，K [M-1]；和K [i]

7. 非叶子节点的指针: P [1]，P [2]，…，P [M]；其中P [1]指向小于K [1]的关键字

子树，P [M]指向其键大于K [M-1]的子树，其他P [i]指向其键属于（K [i-1]，K [i] ）;

8. 所有叶节点都在同一层上；

例如: （M = 3）

从根节点开始的B树搜索，对节点内的关键字（有序）序列执行二进制搜索，如果

匹配结束，否则输入查询关键字范围的子节点；重复直到相应的子指针为

空，或者已经是叶节点；

B树特征:

1. 关键字集分布在整个树中；

2. 任何关键字都会出现，并且只会出现在一个节点中；

3. 搜索可能会在非叶子节点结束；

4. 其搜索性能相当于在完整的关键字集中进行二进制搜索；

5. 自动电平控制；

由于它限制了除根节点以外的其他非叶子节点，因此它至少包含M / 2个子节点，从而确保至少有这些节点

利用率，其最差的搜索性能是:

其中M是非叶子节点的最大数量，N是关键字的总数；

因此B树的性能始终等同于二叉搜索（与M值无关），因此B树平衡没有问题；

由于M / 2的限制，在插入节点时，如果节点已满，则需要将节点拆分为两个以占据每个节点

M / 2个节点；删除节点时，需要合并两个小于M / 2的兄弟节点；

B +树

B +树是B树和多路径搜索树的变体:

1. 它的定义与B树基本相同，除了:

2. 非叶子节点的子树指针的数量与关键字的数量相同；

3. 非叶子节点子树指针P [i]，指向其键值属于[K [i]，K [i + 1]）的子树

（B树是一个开放间隔）；

5. 向所有叶节点添加一个链指针；

6. 所有关键字都出现在叶节点上；

例如: （M = 3）

B +搜索与B树基本相同，不同之处在于B +树仅命中叶子节点（B树可以位于

非叶​​子节点命中），其性能也等同于在完整的关键字集中进行二进制搜索；

B +功能:

1. 所有关键字都出现在叶节点的链接列表（密集索引）中，而链接列表中的关键字恰好

已订购；

2. 不可能击中非叶子节点；

3. 非叶节点等效于叶节点的索引（稀疏索引），叶节点等效于存储

（关键字）数据数据层；

4. 更适合文件索引系统；例如，对于已索引的记录，查找10 <= id <= 20，只要通过根节点搜索id = 10的叶节点，然后根据叶节点的链接列表查找第一个大于20，比每次从10到20搜索根节点的B树搜索都有效.

B *树

它是B +树的变体. 在B +树的非根和非叶节点上添加指向Brother的指针；

B *树定义非叶子节点关键字的数量至少为（2/3）* M，即该块的最小使用率为2/3

（替换B +树的1/2）；

B +树拆分: 当一个节点已满时，将分配一个新节点，并且将原始节点数据的1/2

复制到新节点，最后将新节点的指针添加到父节点； B +树的拆分只会影响原始节点和父节点

该节点不会影响兄弟节点，因此它不需要指向兄弟的指针；

B *树拆分: 当一个节点已满时，如果它的下一个同级节点未满，则它的一部分

将数据移动到同级节点，在原始节点中插入关键字，最后在父节点中修改同级节点的关键字

（因为同级节点的关键字范围已更改）；如果同级节点也已满，则它在原始节点和同级节点之间

在两者之间添加一个新节点，并将数据的1/3复制到新节点，最后将新节点的指针添加到父节点；

因此，B *树分配新节点的可能性低于B +树，并且空间利用率更高；

摘要

B树: 二叉树，每个节点仅存储一个关键字，等于hit，小于左节点，大于

转到右侧节点；

B树: 多路搜索树，每个节点存储M / 2至M个关键字，非叶节点存储指向键

单词范围的子节点；

所有关键字都出现在整个树中，并且只出现一次，非叶子节点可以被击中；

B +树: 在B树的基础上，向叶节点添加一个列表指针，所有关键字都在叶节点中

出现

，非叶子节点用作叶子节点的索引； B +树总是打叶子节点；

B *树: 在B +树的基础上，还为非叶子节点添加链接列表指针，以降低节点的最低利用率.

从1/2增加到2/3;

B + / B *树应用

索引-索引文件和数据文件是分开的，索引文件仅保存数据记录的地址.

索引-表数据文件本身是由B + Tree组织的索引结构. 该树的叶子数据字段包含完整的数据记录. 该索引的键是数据表的主键.

倒排索引-它也可以由B树及其变体实现，但不一定由B树及其变体实现. 例如，Lucene不使用B树结构，因此Lucene可以使用二进制搜索算法快速定位关键字. 在实施过程中，Lucene将以下三列保存为词典文件（术语词典），频率文件（频率）和位置文件（位置）. 词典文件不仅存储每个关键字，还保留了指向频率文件和位置文件的指针，可以通过指针找到关键字的频率信息和位置信息.

关键字文章编号[出现频率]出现位置guangzhou1 [2] 3，6he2 [1] 1i1 [1] 4live1 [2] 2，5,2 [1] 2shanghai2 [1] 3tom1 [1] 1

参考文章

B树和B +树的应用: 数据搜索和索引

B树，B树，B +树，B *树

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