二叉树 AVL树 B树 B+树 红黑树等算法树介绍

二叉树

二叉树是一种特殊的有序树：每个节点至多有两个分支（子节点），分支具有左右次序，不能颠倒。

两种特殊的二叉树：

• 完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点（注意是右边，而不能是左边缺少）。
• 满二叉树：每一层都是满的（除了最后一层，这里的最后一层是指叶节点）。

二叉查找树(Binary Search Tree)

二叉查找树(Binary Search Tree，也叫二叉排序树，即Binary Sort Tree，也称二叉搜索树，有序二叉树(ordered binary tree)，排序二叉树(sorted binary tree) )能够支持多种动态集合操作，它可以用来表示有序集合、建立索引等，因而在实际应用中，二叉排序树是一种非常重要的数据结构。

从算法复杂度角度考虑，我们知道，作用于二叉查找树上的基本操作（如查找，插入等）的时间复杂度与树的高度成正比。对一个含n个节点的完全二叉树，这些操作的最坏情况运行时间为O(log n)。但如果因为频繁的删除和插入操作，导致树退化成一个n个节点的线性链（此时即为一个单链表），则这些操作的最坏情况运行时间为O(n)。为了克服以上缺点，很多二叉查找树的变形出现了，如红黑树、AVL树，Treap树等。

平衡二叉树AVL树

二叉平衡树是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。

平衡因子BF将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF。

多路查找树（B树）

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亿个关键字。我们只要将根结点持久的保留在内存中，那么在这棵树上，寻找一个关键字至多需要读取两次硬盘即可。

多路查找平衡二叉树(B+树)

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

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

红黑树 (Red–black tree)

红黑树是一种自平衡二叉查找树。操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

性质

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是NIL节点）。
• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

参考

https://blog.csdn.net/XieCH1995/article/details/79762786