数据结构中的各种树
目录
一.树的基本术语
二.二叉树
2.1 二叉树的定义
2.2 满二叉树与完全二叉树
三.二叉排序树
四.平衡二叉树
五.B-树
六.B+树
七.红黑树
一.树的基本术语
介绍术语的时候，结合下面这幅图进行解释：
- 结点:树中的一个独立单元。包含一个数据元素及若于指向其子树的分支，如图中的A、B、C、D等。
- 结点的度:结点拥有的子树数称为结点的度。例如，A的度为3，C的度为1，F的度为0。
- 树的度:树的度是树内各结点度的最大值。图所示的树的度为3。
- 叶子:度为0的结点称为叶子或终端结点。结点K、L、F、G、M、I、J都是树的叶子。
- 非终端结点:度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
- 双亲和孩子:结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A，B的孩子有E和F。
- 兄弟:同一个双亲的孩子之间互称兄弟。例如，H、I和J互为兄弟。
- 祖先:从根到该结点所经分支上的所有结点。例如，M的祖先为A、D和H。
- 子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。
- 层次:结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加1。
- 堂兄弟:双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。
- 树的深度:树中结点的最大层次称为树的深度或高度。图所示的树的深度为4。
- 有序树和无序树:如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
- 森林:是m(m≥O)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。
二.二叉树
2.1 二叉树的定义
二叉树(BinaryTree)是n(n≥O)个结点所构成的集合，它或者为空树(n=0);或者为非空树，
对于非空树T:
1.有且仅有一个称之为根的节点；
2.除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点:
1.二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)；
2.二叉树的子树有左右之分，其次序不能任意颠倒。
2.2 满二叉树与完全二叉树
三.二叉排序树
二叉排序树(Binary Sort Tree)又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。
二叉排序树的定义：
1.二叉排序树或者是一棵空树，或者是具有下列性质的二叉树:
2.若它的左子树不空，则左子树上所有结点的值均小千它的根结点的值;
3.若它的右子树不空，则右子树上所有结点的值均大千它的根结点的值;
4.它的左、右子树也分别为二叉排序树。
二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质:中序遍历一棵二叉排序树时可以得到一个结点值递增的有序序列。
四.平衡二叉树
二叉排序树查找算法的性能取决于二叉树的结构，而二叉排序树的形状则取决于其数据集。
如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为O(n); 反之，如果二叉排序 树的结构合理，则查找速度较快，查找的时间复杂度为O(log2 n)事实上，树的高度越小，查找速度越快。因此，希望二叉树的高度尽可能小。
平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)，它是一种特殊的二叉排序树，因由前苏联数学家Adelson-Velskii和Landis提出，所以又称AVL树。
平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：
1.左子树和右子树的深度之差的绝对值不超过1；
2.左子树和右子树也是平衡二叉树；
3.若将二叉树上结点的平衡因子(Balance Factor,BF)定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1；只要二叉树上有一个结点的平衡 因子的绝对值大于1 , 则该二叉树就是不平衡的。
下图结点中的值为该结点的平衡因子
每次插入和删除平衡二叉树的节点后，都可能导致平衡二叉树失去平衡，就需要旋转调平。
五.B-树
线性表的查找（包括顺序查找、二分查找、分块查找）、二叉搜索树、平衡二叉树，这几种查找方式都适用于存储在计算机内存中较小的文件，不适用文件比较大且存放于外存的查找，这些查找方式称为“内查找”。
B-树（也成B树），用于外查找的平衡多叉树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织（比如MySQL的MyISAM存储引擎就是使用B-树）。
B树的定义：一棵m阶的B-树，或为空树，或为满足下列特性的m叉树:
1.树中每个结点至多有m棵子树，也就是说，每个节点的关键字个数最多为m-1个。
2.若根结点不是叶子结点，则至少有两棵子树;
3.除根之外的所有非终端结点至少有m/2棵子树;
4.所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点(失败结点并不存在，指向这些结点的指针为空。
5.所有的非终端结点最多有m-1个关键字。
B-树结点的结构如下图所示：
下面是利用上面的B树节点结构，构造了一个4阶的B树（m=4，每个节点最多有3个关键字），如下图所示：
关于B树定义中的一些注意点：
1.m阶，这个m不是指树的层级，而是指每个节点最多能有m个子节点（最多有m-1个关键字）。
2.引入失败结点是为了便于分析B-树的查找性能，比如上面的叶子节点d，包含1个关键字为11，关键字11的左右分别为指向子节点的指针，现在如果要查询值为10的关键字，发现d节点的关键字为11，那么继续查找d节点的左孩子，发现指向左孩子的指针指向F（failure），表示查找失败，没有关键字为10的数据。
3.按照B树的定义，3阶B树的所有非叶子结点最多可以有2个关键字（此时有3个子树），最少有一个关键字（此时有2个子树），所以3阶B树又称为2-3树；同理，4阶B树又可称为2-4树。
一般情况下，描述一个B树时，会省略关键字的个数，主要突出关键字，然后用指针连接子节点，比如下面这样
上面的图中，最下面一层的空块也就是叶子节点（F节点、失败节点），叶子不包含任何信息。
六.B+树
B+树是B-树的一种变形，更适合做文件索引系统，比如MySQL的InnoDB的索引底层就是使用B+树。
B+树的定义：
1.有n个子树的节点中含有n个关键字；
2.所有的叶子节点中包含了全部的关键字信息，以及指向含这些关键字记录的指针，且叶子节点本身按照关键字的大小自小到大顺序连接；
3.所有的非叶子节点可以看成索引的一部分，节点中仅含有其子树（根节点）中的最大或者最小的关键字；
从上面的定义中，可以与B-树进行对比：B-树是有n个子树的节点中包含n-1个关键字；B-树的叶子节点是失败节点（F节点），不包含任何信息。
下面是一个3阶的B+树：
上图中，叶子节点包含所有的关键字，按照顺序遍历叶子节点，分别是：5，10，15，20，25，28，30，50，55，60，65，75，80，85，90，95，是按照从小到大排序的。
可以通过B+树的叶子节点直接访问其他叶子节点，而不需要返回根节点（在B-树中，如果要通过一个叶子节点访问其他叶子节点，则需要返回上一层或者根节点）。
七.红黑树
AVL树的插入和删除节点都可能涉及到平衡调整，因为AVL是严格平衡的，所以当进行删除和插入节点的时候，进行调整平衡是比较费时的，另外AVL树的每个节点都会记录左右子树的高度差，如果高度差的绝对值超过1，则需要进行调平，保存高度差的整型变量也会占用内存。
红黑树（Red Black Tree） 是一种自平衡二叉查找树，红黑树降低了平衡性要求，达到局部平衡。
红黑树中的节点使用“红”和“黑”进行着色（也就是用一个bool值表示红或黑，比如true为红，false为黑），红黑树并不是严格的平衡二叉树
红黑树的性质：
1.红黑树的每个节点，要么是红色，要么是黑色；
2.根节点永远是黑色；
3.“红色”节点的两个子节点必须是黑色的，也就是“不允许出现两个连续的红色节点”，但是可以出现连续的黑色节点；
4.对于每个节点，从该节点到其所有子孙叶节点的路径中，所包含的黑色节点数量必须相同；
5.扩充外部叶节点都是黑色节点（扩充外部叶节点也就是叶子节点的左右子节点，虽然叶子节点的左右节点都为null，但是红黑树认为叶子节点的左右节点都为黑节点）；
在最坏条件下，红黑树也能在O(log n)的时间内做查找、删除、插入操作，n是指树中的元素个数。
红黑树与AVL树的区别：
1.AVL（平衡二叉树）的查询性能更高，因为AVL比红黑树更加严格平衡（AVL调平的频次较高）；
2.红黑树的插入和删除的速度更快，因为调整的频次较低，甚至不需要调整；
3.AVL需要在每个节点增加一个整数来记录左右子树的高度差；而红黑树的每个节点只需要使用一个布尔值标志其实red or black。