# Java - 数据结构之树 ## 基本概念 树（Tree）不是线性表，而是一种描述非线性层次关系的数据结构，描述的是一对多的数据结构。 ● 结点：Node，有的资料也叫做节点。
● 根结点（Root）：没有父结点的结点，一棵树只能有一个根结点。
● 兄弟结点（Siblings）：拥有同一个父结点的结点，它们是父结点的子结点。
● 孩子、双亲（Child、Parent）：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
● 结点的度（Degree）：一个结点所包含的子树的数量，即子结点的数量。
● 树的度：该树所有结点中最大的度。
● 叶子结点（Leaf）：树中度为零的结点，也叫终端结点。
● 分支（Branch）：至少有一个孩子的结点，也叫非终端结点。
● 祖先（Ancestor）：结点的祖先是从根到该结点所经分支上的所有结点。
● 后代（Descendant）：以某结点为根的子树中的任一结点都称为该结点的后代。
● 边（Edge）：一个结点和另一个结点之间的连接被称为边。
● 路径（Path）：连接结点和其后代的结点之间的（结点，边）的序列
● 层次（Level）：从根结点开始算，根结点是第一层，依次往下。（也可以把根结点作为第0层）
● 结点的高度（Height of node）：该结点和某个叶子之间存在的最长路径上的边的个数。
● 树的高度（Height of tree）：树的高度是其根结点的高度。
● 结点的深度（Depth of node）：从树的根结点到该结点的边的个数。**和高度的区别在于，深度是从根结点开始往下到自身结点；高度是从自身结点往下到叶子结点。**
● 树的深度（Depth of tree）：树中结点的最大层次。树的高度等于树的深度。
● 无序树：树中任意结点的子结点之间没有顺序关系，这种树称为无序树，也称为自由树。
● 有序树：树中各结点的子结点之间从左到右按一定次序排列的树。
● 森林：n(n>=0)棵互不相交的树的集合。 ## 树的存储结构 ● 双亲表示法：在每个结点的结构中，通过一个字段来记录双亲结点在数组中的位置。
● 孩子表示法：每个结点有多个指针域，其中每个指针都指向一颗子树的根结点。
● 孩子兄弟表示法：任意一棵树，其结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，通过设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。 双亲表示法可以和孩子表示法合并组合成双亲孩子表示法。 孩子兄弟表示法可以把一颗复杂的树变成一颗二叉树。 * [树的双亲表示法，孩子表示法以及孩子兄弟表示法](https://segmentfault.com/a/1190000038745989) ## 二叉树（Binary Tree） 每个结点最多只能有两个子结点的树，即为二叉树。也就是说，二叉树中不存在度大于2的结点；且二叉树的子树有左右之分，其次序不能颠倒。 ### 二叉树的性质 ● 若二叉树的层次从1开始，则在二叉树的第i层至多有2^(i-1)个结点(i>=0)
● 若空树的高度为0，高度为k的二叉树最多有2^k - 1个结点(k>=-1)。
● 对任何一棵二叉树，如果其叶子结点（度为0）数为m, 度为2的结点数为n, 则m = n + 1
前两个性质其实就是二进制数的性质。 ### 斜树 所有结点都只有左子树的二叉树，叫左斜树。相对地，所有结点都只有右子树的二叉树，叫右斜树。斜树相当于树结构退化成了链表。 ### 完美二叉树（Perfect Binary Tree） 有些资料将完美二叉树翻译为满二叉树，区别于完满二叉树。 一棵树除了叶子结点外的其他结点的度都为2，且叶子结点都在同一深度，即叶子结点必然都在最后一层。 >A Perfect Binary Tree (PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2. 完美二叉树拥有最多的结点数量。 ### 完全二叉树（Complete Binary Tree） 完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，且叶子结点必须全部靠左对齐。 换言之，完美二叉树是一棵完全二叉树，反之则未必。 >A Complete Binary Tree (CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. ### 完满二叉树（Full Binary Tree） 完满二叉树的所有非叶子结点的度都是2，换言之，如果一个结点有子结点，则必然是两个子结点。 完美二叉树也叫Strictly Binary Tree。完美二叉树是一棵完满二叉树，反之则未必。 >A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children. ## 二叉树的遍历 先序遍历（前序遍历）：先访问根结点，然后左子树，最后右子树。 中序遍历：先访问左子树，然后根结点，最后右子树。 后序遍历：先访问左子树，然后右子树，最后根结点。 层序遍历：从上到下，从左到右依次遍历每一层中的每一个结点。 ## 深度优先搜索（DFS） DFS是Depth-First-Search的简称，思路是从根结点开始，沿着一条路径走到底，如果不能到达目标解，则返回上一个结点，然后沿着另一条路径走到底。 DFS通过栈来实现，一次压栈代表遍历一个结点，沿着路径走到底，通过出栈来返回上一个结点，然后继续将邻接的尚未遍历的结点压栈来继续走到底，一直到找到目标解或者遍历所有结点为止。 DFS易于用递归实现，时间消耗较小，但容易发生爆栈。虽然可以寻找有解，但无法找到最优解。 ## 广度优先搜索（BFS） BFS是Breadth-First-Search的简称，思路是从根结点开始，沿着宽度来遍历邻近的结点，即遍历根结点的子结点，如果没有找到目标解，则继续遍历这些结点的尚未遍历的子结点，直到找到目标解或者遍历所有结点为止。 BFS通过队列来实现，每次遍历结点时将其入队，然后遍历队列头部的结点所有邻接的尚未遍历的结点并入队，然后将头部结点出队。一直循环这个过程，直到找到目标解或遍历完全部结点。 BFS可以找到最短路径，但如果树的层次较大、结点数较多，BFS会内存消耗十分严重。 ## 动态查找树 ### 二叉查找树（排序二叉树） 二叉查找树，即Binary Search Tree，也叫二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： ● 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
● 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
● 任意结点的左、右子树也分别为二叉查找树；
● 没有键值相等的结点；
● 二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。 二叉查找树的优势在于查询、插入的时间复杂度较低，为O(logn)。但是当插入的数据为一系列有序的数据时，此时的树为斜树，树结构会退化成链表，此时查询、插入效率大大降低，为O(n)。 ### 二叉树的旋转 二叉树可以通过旋转来来修改树的深度，以此调节二叉树的平衡度。旋转分为左旋和右旋。 对某个结点进行左旋，就是把该结点旋转为左结点。右旋与之相对，就是把结点旋转为右结点。旋转之后要依然保持二叉查找树的性质，效果如下： ``` z x / \ / \ --(对x结点左旋)--> x b y z / \ / \ y a a b y x / \ / \ --(对x结点右旋)--> a x y z / \ / \ b z a b ``` ### 平衡二叉树（AVL树） 保持二叉查找树的平衡并不容易，为了避免二叉查找树在某些极端情况下退化为链表，就有了平衡二叉树的概念。 平衡二叉树（Balanced Binary Tree），是自平衡的二叉查找树（Self-balancing binary search tree），其性质如下： ● 要么是棵空树，要么其根结点左右子树的深度之差的绝对值不超过1；
● 其左右子树也都是平衡二叉树；
● 二叉树结点的平衡因子定义为该结点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。 在插入或者删除结点时，为了满足平衡二叉树的性质，就需要进行自平衡操作，即二叉树的旋转。 AVL树是最早发明的自平衡二叉查找树，是最原始典型的平衡二叉树。AVL指的是发明该树的两个作者名字的简称，通常说的平衡二叉树指的是AVL树。AVL树的每个结点都保存着一个额外的值：结点的平衡因子，即为左子树减去右子树的深度。 也可以这样理解：如果一个结点A只存在左结点，则结点A的平衡因子为1；若只存在右结点，则结点A的平衡因子为-1；若不存在子结点，或者左右子结点都存在，则平衡因子为0。 #### AVL树的旋转 AVL树的旋转类型有4种：LL（left-left）旋转、LR（left-righ）旋转、RR（right-right）旋转和RL（right-left）旋转。 LL型表示在结点X的左结点的左结点上添加的新的结点A，此时通过对结点X进行单次右旋即可实现平衡。 ``` y x / \ / \ --(对x结点右旋)--> a x y z / / \ / \ （新结点）A b z a b / A（新结点） ``` RR型表示在结点X的右结点的右结点上添加的新的结点A，此时通过对结点X进行单次左旋即可实现平衡。 ``` z x / \ / \ --(对x结点左旋)--> x b y z / \ \ / \ y a A（新结点） a b \ A（新结点） ``` LR型双旋转表示在结点X的左结点的右结点上添加的新的结点A，此时通过先对结点y进行左旋（RR型旋转），再对结点x右旋（LL型旋转）即可实现平衡。 ``` x b x / \ / \ / \ --(对y结点左旋)--> b z --(对x结点右旋)--> y x y z / \ / / \ / \ y A（新结点） a A z a b / （新结点） \ a A（新结点） ``` RL型双旋转表示在结点X的右结点的左结点上添加的新的结点A，此时通过先对结点y进行左旋，再对结点b右旋即可实现平衡。也就是说，先对祖父结点左旋（RR型旋转），再对父节点右旋（RR型旋转）。 ``` x a x / \ / \ / \ --(对z结点右旋)--> y a --(对x结点左旋)--> x z y z / \ / \ \ / \ （新结点）A z y A b a b \ （新结点） / b A（新结点） ``` * [平衡二叉查找树（AVL）的构建——左旋右旋](https://blog.csdn.net/qq_38596491/article/details/108218913) ### 红黑树（Red-Black Tree） 红黑树也是一种自平衡的二叉查找树，在二叉查找树的基础上给每个结点增加了一个颜色属性，结点的颜色只能是红色或黑色。其性质如下： 1）结点是红色或黑色；
2）根结点只能是黑色；
3）红黑树中所有的叶子结点后面再接上左右两个黑色的空结点（NIL结点），此时空结点变成了叶子结点。也就是说，红黑树的叶子结点都是黑色的空结点；
4）红色结点的父结点和左右孩子结点都是黑色，也就是说，从每个叶子到根的所有路径上不能有两个连续的红色节点；
5）在任何一棵子树中，从根结点向下走到空结点的路径上所经过的黑结点的数目相同，从而保证是一个平衡二叉树。 红黑树的自平衡操作有两种：变色和旋转。红黑色的自平衡比较复杂，不同的插入、删除结点场景对应的操作各有不同。 在插入新结点时，新结点的颜色为红色，这是为了不影响到上述的性质5。接着为了满足性质4就需要进行变色，有时候只靠变色是无法保持平衡的，此时就还需要进行旋转，需要具体情况具体分析。 平衡二叉树（AVL树）是严格平衡的二叉查找树，平衡因子不大于1，以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN)的查找时间复杂度。而红黑树则不同，它是相对接近平衡的二叉树，只需要确保没有一条路径会比其他路径长出俩倍即可。 * [30张图带你彻底理解红黑树](https://www.jianshu.com/p/e136ec79235c) 红黑树是一种应用很广的数据结构，Java的TreeSet和TreeMap底层就使用了红黑树。红黑树是一棵完满二叉树。 ### 哈夫曼树（最优二叉树） 哈夫曼树是Huffman Tree的音译，是一种带权路径长度最短的二叉树，也叫最优二叉树。哈夫曼编码就是对哈夫曼树的一种应用。 如果一个结点拥有权值，则该结点的带权路径长度WPL为其权值乘以根结点到该结点路径的积。对于哈夫曼树，权值较大的结点离根较近。 构建方式如下： 1）将所有左，右子树都为空的作为根结点。
2）在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。
3）从森林中删除这两棵树，同时把新树加入到森林中。
4）重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。 * [结构（哈夫曼树）](https://www.cnblogs.com/pixiuart/p/5976795.html) ## 多路查找树（muitl-way search tree） 对于在内存中查找结构来说，红黑树的效率已经很好了。但内存中的树节点存储的元素数量是有限的，在查找数据量非常大的场景下，不可能将所有数据都存放到内存中，必须在磁盘中建立查询结构，这样查询时还会涉及到磁盘I/O操作。并且对于二叉查找树结构，在数据量很大时会导致树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。 也就是说，所有的二叉查找树结构在磁盘中都是低效的，因此就有了多路查找树。 多路查找树的每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。多路查找树适用于读写相对大的数据块的存储系统，例如磁盘。 ### B树（B-tree） B树是平衡多路查找树，英文名是B-tree，有的翻译为B-树，B就是balanced。B树满足以下性质： 1）根结点至少有两个子女。
2）每个中间结点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3）每一个叶子结点都包含k-1个元素，其中 m/2 <= k <= m
4）所有的叶子结点都位于同一层。
5）每个结点中的元素从小到大排列，结点当中k-1个元素正好是k个孩子包含的元素的值域分划。
相比于磁盘I/O的速度，内存中的耗时几乎可以省略，所以只要B树的高度足够低，I/O次数足够小，就可以提升查询性能。 B树的增加删除同样遵循自平衡的性质，有旋转和换位。 B树的应用是文件系统及部分非关系型数据库索引。 ### B+树 B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度；所以通常用于关系型数据库（如MySQL）和操作系统的文件系统中。B+ 树元素自底向上插入，这与二叉树恰好相反。 B+树是B树的一种变体，在B树的基础上，为叶子结点增加链表指针（B树+叶子有序链表），所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引。这意味着B+树的查找效率更加稳定，因为所有叶子结点都处于同一层中，而且查找所有关键字都必须走完从根结点到叶子结点的全部历程。因此同一颗B+树中，任何关键字的查找比较次数都是一样的。而B树就不一定了，可能查找到某一个非终结点就结束了。 B+树的非叶子结点不保存数据，只保存子树的临界值（最大或者最小），所以同样大小的结点，B+树相对于B树能够有更多的分支，使得这棵树更加矮胖，查询时做的I/O操作次数也更少。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。 ### B*树 B*树是B+树的变体，在B+树的基础上，为非根结点和非叶子结点再增加指向兄弟的指针。 ### R树 R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。R指的就是Rectangle矩形。 ## 参考链接 * [数据结构复习之树](https://www.cnblogs.com/changyaohua/p/4652184.html) * [完美二叉树, 完全二叉树和完满二叉树](https://www.cnblogs.com/idorax/p/6441043.html) * [基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）](https://www.jianshu.com/p/bff70b786bb6) * [数据结构之树](https://blog.csdn.net/wannuoge4766/article/details/83998377)