本篇文章主要是整理一下 有关二叉树、满二叉树、完全二叉树、红黑树、二叉搜索树、平衡二叉树、B树、B+树的基础知识点。为了方便学习和今后的不断深入研究，现整理如下。如有存在问题的地方，欢迎指正。

 

1、二叉树：

1. 本身是有序树；（默认）查看 有序树 中声明：注意：若不特别指明，一般讨论的树都是有序树。
2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

二叉树有下面的性质：

1. 二叉树中，第 i 层最多有 2i-1 个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2*n2。所以，n 用另外一种方式表示为 n=n1+2*n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

 

2、满二叉树：

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树

满二叉树性质：

1. 满二叉树中第 i 层的节点数为 2^(i-1) 个。
2. 深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子数为 2^(k-1)。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。

 

3、完全二叉树：

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树

（顺序存储结构，非完全二叉树可以通过转换完全二叉树）

对于任意一个结点 i ，完全二叉树有如下性质：

1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2*i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2*i 。
3. 如果 2*i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2*i+1 。

以上借鉴于什么是二叉树，二叉树及其性质详解。

---

4、二叉搜索树（BST）

 

1.  任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值
2.  任意节点的右子树不空, 则右子树上所有节点均大于它的根节点的值
3.  任意节点的左,右子树也分别为二叉查找树
4.  没有键值相等的节点

5、平衡二叉树（AVL）

 

1. 每棵子树中的左子树和右子树的深度差不能超过 1；
2. 二叉树中每棵子树都要求是平衡二叉树

 

6、红黑树（RBT）：

 

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

关于以上5点可以总结为：从根到叶子的最长路径最多不会超过最短路径的两倍 ，解释如下：这主要是考虑两个极端的情况，由性质 4 和 5 我们可以知道在一棵红黑树上从根到叶子的最短路径全部由黑色结点构成，而最长结点则由红黑结点交错构成（始终按照一红一黑的顺序组织），又因为最短路径和最长路径的黑色结点数目是一致的，所以最长路径上的结点数是最短路径的两倍。

对于这个总结我一开始是，不清楚为什么的。直到这篇文章，感谢分享：那些年，面试被虐过的红黑树

 

 

7、B树

下图很好展示了B树：

下面一个图，更加详细的讲诉了B树中每个结点包含的东西：

图中：

• 小红方块表示对应关键字所代表的文件的存储位置，实际上可以看做是一个地址，比如根节点中17旁边的小红块表示的就是关键字17所对应的文件在硬盘中的存储地址。
• P是指针，不用多说了，需要注意的是：指针，关键字，以及关键字所代表的文件地址这三样东西合起来构成了B树的一个节点，这个节点存储在一个磁盘块上
   

 

 

 

8、B+树

如下图；

1. 有n棵子树的结点中含有n 个关键字；
2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
3.  所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

 

为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？

1) B+-tree的磁盘读写代价更低

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

   

2) B+-tree的查询效率更加稳定

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

 

以上B树和B+树内容，来源于--JUly七月的博客 从B树、B+树、B*树谈到R 树。大佬就是大佬。

 

---

对于相关的优缺点分析，后续更新。