二叉查找树BST

二叉查找树，也称二叉搜索树，或二叉排序树。其定义为，要么是一颗空树，要么就是具有如下性质的二叉树：

（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2） 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3） 任意节点的左、右子树也分别为二叉查找树；

（4） 没有键值相等的节点。

平衡二叉树AVL

平衡二叉搜索树，又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树总结：

• 查询时间复杂度O(logN)
• 插入操作：左左、左右、右左、右右4种，插入操作O(1)
• 删除操作：比较复杂，包括待删除节点是：（1）叶子节点；（2）只有左或右子树；（3）既有左子树也有右子树

平衡二叉树是一棵高度平衡的二叉树，所以查询的时间复杂度是 O(logN) 。插入的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，插入复杂度是 O(1) ，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树。

红黑树

红黑树可以算是树状结构中的“明星”了，应该计算机专业都听过红黑树这个专业名词，而且红黑树的应用也很广泛，比方说， java 集合中的 TreeSet 和 TreeMap ，以及 jdk8 的 HashMap 链表长度超过7之后会转成红黑树等等。但实际上红黑树却很复杂，他并不是像前面讲过的树一样是棵平衡树，即红黑树并没有定义从根节点到叶子节点的长度一致或高度差为1，然而他却能保证树大致上是平衡的—-从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，这需要从他的性质中去推导出来。先来看一下红黑树的性质：

（1）节点是红色或黑色；

（2）根节点是黑色；

（3）每个叶节点（NIL节点，空节点）是黑色的；

（4）从每个叶子到根的所有路径上不能有两个连续的红色节点；

（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

• 红黑树特点：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

AVL树 和 红黑树对比：

AVL树是高度平衡的树（左右子树高度差为1），所以不管是插入节点也好，删除节点也好，都会很容易导致树的不平衡，从而引发调整，而红黑树不是严格的平衡树，节点插入与删除，并不容易会导致树进行调整，所以这点才是红黑树综合性能比 AVL树 好的原因。

————————————————
原文链接：https://blog.csdn.net/qq_25940921/article/details/82184055

B树（多路平衡查找树）

如果前面的2-3树与2-3-4树理解了，B树也就理解了，因为2-3树就是3阶的B树，2-3-4树就是4阶的B树。所以，对于B树的性质，根据2-3-4树都可以推导出来了，即，

  一颗m阶的B树（B-tree） 定义如下：

（1）每个节点最多有 m-1 个key；

（2）根节点至少有1个key；

（3）非根节点至少有 Math.ceil(m/2)-1 个key；

（4）每个节点中的key都按照从小到大的顺序排列，每个key的左子树中的所有key都小于它，而右子树中的所有key都大于它；

（5）所有叶子节点都位于同一层，即根节点到每个叶子节点的长度都相同。

  如下图是一棵4阶B树（2-3-4树）

B+树

B+树在B树的基础上做了优化，它与B树的差异在于：

（1）有 k 个子节点的节点必然有 k 个key；

（2）非叶子节点仅具有索引作用，跟记录有关的信息均存放在叶子节点中。

（3）树的所有叶子节点构成一个有序链表，可以按照key排序的次序遍历全部记录。

B树 对比 B+树

• B+树的优点在于：
  • 1.由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
  • 2.B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

• B树也有优点，其优点在于：
  • 由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

B*树

在B+ 树非根和非叶子结点再增加指向兄弟的指针

• B-树适用场景：

  • 文件系统：B-树通常用于文件系统的索引结构，因为它可以更好地处理磁盘上的随机读写操作。
  • 数据库管理系统：在某些情况下，B-树可以用于数据库管理系统中的索引，特别是在存储引擎需要支持随机访问的情况下。

• B+树适用场景：

  • 数据库索引：B+树是最常见的数据库索引结构，适用于数据库系统中的绝大多数情况。它在范围查询、按顺序遍历和插入/删除操作方面表现出色。
  • 文件系统：虽然B-树也用于文件系统，但B+树同样适用，尤其在需要支持大文件的情况下。

• B*树适用场景：

  • 高度平衡要求：B*树通常用于需要维护高度平衡的场景，以减少树的高度。这在某些存储引擎中可能会有所帮助。
  • 高度不断增长的情况：如果数据集的大小在不断增长，而且需要保持树的平衡性，B*树可能比传统的B-树更适合。