B树，B+树，二叉查找树，平衡二叉树，红黑树

树、根节点、父节点、子节点

1. 没有父节点的节点称为根节点
2. 除空树外每棵树只有一个根节点
3. 每个节点都只有有限个子节点或无子节点
4. 每个非根节点有且只有一个父节点
5. 树里面没有环路，如果从一个节点出发，除非往返，否则无法回到起点
6. 叶节点：没有子节点的节点。
7. 兄弟节点：有共同父节点的一些子节点。
8. 祖先：节点的父节点、父节点的父节点，以此类推，直到根节点为止。
9. 后代：节点的子节点、子节点的子节点，以此类推，直到叶节点为止。

举例：

1. 节点 G、H、I、J、L、N 没有子节点，它们是叶子节点。

2. B、C、D、E、F 有共同的父节点 A，它们是兄弟节点，同理 G 和 H 以及 L 和 N 也是兄弟节点。

3. 考察节点 L，其父节点为 K，K 的父节点为 F，F 的父节点为 A，A 为根节点，因此 K、F、A 为 L 的祖先。

4. 考察节点 F，其子节点，子节点的子节点，直到叶节点如下，因此 K、L、N 为 F 的后代。

路径、路径长度、节点的深度、树的高度

1. 路径：连接节点和其中一个后代的一系列的边。

2. 路径长度：路径里边的数目。

3. 深度：也叫层数，是连接节点与根节点的路径长度 1。

4. 高度：树里最长路径的长度 1，也就是叶节点的最大层数。

5. 考察节点 A 以及它的一个后代 L，连接 A 和 L 的一系列边为 AF、FK、KL，因此 A -> F -> K -> L 是 A 到 L 的路径。其中的路径个数为 3 个，因此路径长度为 3。

6. A 是这棵树的根节点，考察节点 L，前面我们提到 A 到 L 的路径长度为 3，因此 L 的深度为 3 1 = 4。

7. 通过观察， L 是这棵树里最深的叶节点，它到根节点是这棵树里的最长路径长度，因此这棵树的高度也就是 4。

树结构的性质

1. 非空树的结点总数等于树种所有结点的度之和加 1
2. 度为 K 的非空树的第 i 层最多有 ki-1 个结点(i >= 1)
3. 深度为 h 的 k 叉树最多有(kh - 1)/(k - 1)个结点
4. 具有 n 个结点的 k 叉树的最小深度为 logk(n(k-1) 1))
5. 结点的度：结点拥有的子树的数目。eg：结点 A 的度为3
6. 树的度：树种各结点度的最大值。eg：树的度为3
7. 叶子结点：度为 0 的结点。g：E、F、C、G 为叶子结点
8. 孩子结点：一个结点的子树的根节点。eg：B、C、D 为 A 的子结点
9. 双亲结点：B 为 A 的子结点，那么 A 为 B 的双亲结点
10. 兄弟结点：一个双亲结点结点的孩子互为兄弟结点。eg：B、C、D 为兄弟结点
11. 结点的层次：根节点为第一层，子结点为第二层，依次向下递推…eg：E、F、G 的层次均为 3
12. 树的深度：树种结点的最大深度。eg：该树的深度为 3
13. 森林：m 棵互不相交的树称为森林

二叉树

二叉树是对普通树形结构进行限定得到的一种特殊的树，规定树中节点的度不大于2，当节点有两个子节点，也就是有两颗子树时，它们有左右之分，分别被称为左子树和右子树，左子树和右子树又同样都是二叉树。

二叉树性质

1. 二叉树的第i层上至多有2^(i-1)（i≥1）个节点
2. 深度为h的二叉树中至多含有2^h-1个节点
3. 若在任意一棵二叉树中，有n个叶子节点，有m个度为2的节点，则必有n=m 1
4. 具有n个节点的满二叉树深为log(2n 1)
5. 若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点
   1. 当i=1时，该节点为根，它无双亲节点
   2. 当i>1时，该节点的双亲节点的编号为i/2
   3. 若2i≤n，则有编号为2i的左节点，否则没有左节点
   4. 若2i 1≤n，则有编号为2i 1的右节点，否则没有右节点

满二叉树与完全二叉树

满二叉树： 如果一棵二叉树的任意一个结点或者是叶子结点，或者有两棵子树，同时叶子结点都集中在二叉树的最下面一层上，这样的二叉树称为满二叉树

完全二叉树： 若二叉树中最多只有最下面两层结点的度小于 2 ，并且最下面一层的结点（叶子结点）都依次排列在该层最左边的位置上，具有这样结构特点的树结构称为完全二叉树。

二叉树的遍历

遍历有三种方式：前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树接地那遍历的先后顺序

1. 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树——根左右

2. 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树——左根右

3. 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身——左右根

二叉查找树

1. 是二叉树中最常用的一种类型。
2. 支持快速查找一个数据，还支持快速插入、删除一个数据。
3. 任意一个节点，其左子树的每个节点的值都要小于这个节点的值，而右子树节点的值都应大于这个节点的值。
4. 二叉查找树不管是插入、删除还是查找操作，时间复杂度都跟树的高度成正比，即O（height）。
   

查询

如果需要查找一个数，首先取根节点，如果它等于要查找的数据，则直接返回，如果小于要查找的数据，则在右子树中继续查找，如果大于要查找的数据，则在左子树中继续查找，也就是二分查找的思想，这样一直递归。

插入

二叉树的插入类似于查找过程，首先还是从根节点开始，然后依次比较要插入的数据与接地那的关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点的数据小，也是类似的操作。

删除（复杂)

1. 如果要删除的节点没有子节点，我们只需要直接将父节点中指向要删除节点的指针置为null。比如删除图中的节点55。
2. 如果要删除的节点只有一个子节点，我们只需要更新父节点中指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如删除图中的节点13。
3. 如果要删除的节点有两个子节点，这时我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上，然后再删除这个最小节点。比如删除图中的节点18。

二叉查找树的时间复杂度分析

1. 二叉查找树，除了插入、删除、查找之外，还可以支持快速查找最大节点、最小节点、前继节点、后继节点。同事二叉查找树还有一个重要特性，就是 中序遍历二叉树，可以输出有序的数据序列，时间复杂度为O（n），非常高效。

2. 进一步思考： 二叉查找树可以支持快速插入、删除、查找操作，各个操作的时间复杂度与树的高度成正比，最理想情况下，时间复杂度是O(logn)。

3. 但在极端情况下，比如频繁的删除等操作，二叉树会退化成一个链表，那么时间复杂度就变成了O(n)。

4. 因此，为了避免这种极端情况，后来又设计一种平衡二叉树，平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn）。

平衡二叉树

平衡二叉树是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis联合提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础上增加了“平衡”的要求，需保证其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度因子之差称为平衡因子。

对于AVL树，不管是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡。由于旋转比较耗时，所以AVL树适合用于插入与删除次数比较少，但查找多的情况。

条件

1. 必须是二叉查找树。
2. 每个节点的左子树和右子树的高度差至多为1。
3. 左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。
   
4. AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。
5. 如果需要查找的集合本身没有顺序，在频繁查找的同时也经常的插入和删除，AVL树是不错的选择。不平衡的二叉查找树在查找时的效率是很低的，因此，AVL如何维护二叉树的平衡是学习重点。

平衡二叉树带来的问题

虽然平衡二叉树解决了二叉查找树可能退化了链表的极端情况，并且能够把查找时间控制在O（logn），所以”平衡“的意思就是为了使性能不退化。但是由于平衡二叉树严格的定义：每个节点的左子树和右子树的高度差至多等于1，导致每次在插入或者删除的时候，为了符合平衡二叉树严格的条件，需要进行一些操作来进行调整，比如左旋、右旋等操作，使其再次符合平衡二叉树的条件。

很明显，如果要是再插入和删除非常频繁的场景下，平衡二叉树每一次更新都必须要进行调整，这样太耗时了，性能也会受到很大影响。

因此，为了避免平衡二叉树在频繁更新过程中，所带来的维持树结构的时间消耗，从而引入了红黑树。

红黑树

红黑树也是一颗二叉查找树，需要为每个节点存储节点的颜色，可以是红或黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，来确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树。

由于是弱平衡二叉树，那么在相同的节点情况下，AVL树的高度小于等于红黑树的高度，相对于要求严格的AVL树来说，它的旋转次数少，所以对于插入，删除操作较多的情况下，用红黑树的查找效率会更高一些。

特点

1. 每个节点非红即黑
2. 根节点是黑的
3. 每个叶子节点（叶子节点即树尾端NULL节点）都是黑的
4. 每条路径都包含相同的黑节点
5. 如果一个节点是红的，那么它的两儿子都是黑的
6. 对于任意节点而言，其到叶子点的每条路径都包含相同数目的黑节点

应用

1. 广泛用于C 的STL中，如 map 和 set 是用红黑树实现的
2. Linux的进程调度用红黑树管理进程控制块，进程的虚拟内存空间都存储在一颗红黑树上，每个虚拟内存空间都对应红黑树的一个节点
3. IO多路复用的 epoll 采用红黑树组织管理socket fd，以支持快速的增删改查
4. Nginx中用红黑树管理定时器，可以快速得到距离当前最小的定时器

Trie树

1. Trie树又被称为前缀树、字典树是一种用于快速检索的多叉树结构。
2. 字典树把字符串看成字符序列，根据字符串中字符序列的先后顺序构造从上到下的树结构，树结构中的每一条边都对应着一个字符。
3. 字典树上存储的字符串被视为从根节点到某个节点之间的一条路径，并在终点节点上做个标记"该节点对应词语的结尾"，正因为有终点节点的存在，字典树不仅可以实现简单的存储字符串，还可以实现字符串的映射，只需要将相对应的值悬挂在终点节点上即可。

B树

B树是一个多路平衡查找树，B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，同时数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况，而B树是解决这个问题的很好的结构。

要想了解B树需要了解一个很重要的概念，B树中所有节点的度的最大值称为B树的阶，记为m，这是一个跟重要值，也就是说m阶B树指的是节点度最大为m的B树。

特点

1. 每个节点最多只有m个子节点
2. 根结点的儿子数为[2, m]
3. 除根结点以外的非叶子结点的儿子数为[m/2, m]，向上取整
4. 非叶子结点的关键字个数=子节点数-1
5. 所有叶子都出现在同一层
6. k个关键字把节点拆成k 1段，分别指向k 1个儿子，同时满足查找树的大小关系
7. 非叶子节点中不仅包含索引，也会包含数据
8. B树是一种自平衡的搜索树
9. 多路，非二叉树
10. 每个节点既保存索引，又保存数据
11. 搜索时相当于二分查找
12. B树：每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。

应用

B树是一种平衡的多路查找树，主要用作文件的索引。其优势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询，有很多基于频率的搜索是选用B树，越频繁查询的结点越往根上走，前提是需要对查询做统计，而且要对key做一些变化。

B 树

B 树是b树的一种变体，查询性能更好，m阶的b 树具有以下特征：

1. 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）
2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
3. 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字
4. 通常在b 树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
5. 同一个数字会在不同节点中重复出现，根节点的最大元素就是b 树的最大元素
6. B 树：内部结点(非叶子节点)中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
7. 多路非二叉
8. 只有叶子节点保存数据
9. 搜索时相当于二分查找
10. 增加了相邻结点的指向指针。

与b树区别

1. B 树内节点不存储数据，B树内节点存储数据。所以B 树将业务数据和索引数据分离，减少了磁盘I/O次数。
2. 因为B 树所有 data 存储在叶节点导致查询时间复杂度固定为O(logn)。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
3. B 树的遍历更加高效，B树需要以中序的方式遍历节点，而B 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便
4. B 树父节点存有右孩子的第一个元素的索引。

B 树（B 树是B树的变种）

1. 多路非二叉
2. 只有叶子节点保存数据
3. 搜索时相当于二分查找
4. 增加了相邻结点的指向指针。

区别

1. B 树内节点不存储数据，B树内节点存储数据。所以B 树将业务数据和索引数据分离，减少了磁盘I/O次数。
2. 因为B 树所有 data 存储在叶节点导致查询时间复杂度固定为O(logn)。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
3. B 树的遍历更加高效，B树需要以中序的方式遍历节点，而B 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便
4. B 树父节点存有右孩子的第一个元素的索引。

优势

1. B tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多，相对来说IO读写次数也就降低了。

2. 由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3. B 树支持范围遍历，只要遍历叶子节点就可以实现整棵树的遍历，而在数据库中基于范围的查询是非常频繁的，这一点要明显由于B树。

由于拥有以上特点，B 广泛应用于文件存储系统以及数据库系统中。

mysql和mongo的选择

1. MongoDB使用B树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。

2. Mysql作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B 树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。

这篇好文章是转载于：学新通技术网