深入理解java的数据结构之树详解篇一（二叉树的基础概念篇）_java树

树的基础

树的基本分类与构造：

树

树是一种数据结构，它是n(n>=0)个节点的有限集，n = 0时称树为空树，当n > 0时，n个有限集构成一个有层次感的数据结构。

树和线性表有很大的区别，线性表的关系是一对一的，而树的节点的对应关系是一对多的，树具有以下几个特点：

1、当 n > 0时，树的根节点只有一个，不存在有多个根节点的情况
2、每个节点具有0个或者多个子节点，除了根节点外，每个节点有且仅有一个父节点，但是根节点没有父节点。

树的相关概念

根节点： 一棵树中没有双亲节点的节点称之为根节点。
子树： 除了根节点外，每个子节点都可以分为多个不相交的子树。
孩子与双亲： 若一个节点有子树，那么该节点称为子树根的“双亲”，子树的根就是该节点的孩子。
节点的层次： 从根节点开始定义，根节点为第一层，根节点的子节点为第二层，以此类推。
节点的度： 一个节点拥有子树的数目。
兄弟节点： 具有相同父节点的节点。
堂兄弟节点： 双亲在同一层的节点
树的高度或深度： 树中节点的最大层次。
叶子： 没有子树，也就是度为0的节点。
分支节点： 除了叶子节点之外的节点，也就是度不为0的节点。
内部节点： 除了根节点之外的分支节点，
有序树： 树中节点各子树之间的次序是最重要的，不可以随意交换位置。
无序树： 树中节点各子树之间的次序是不重要的可以随意交换位置。
森林： 0或多颗互不相交的树的集合。

二叉树

二叉树： 一颗二叉树是结点的一个有限集合，该集合为空，或者是由一个根结点加上两棵别称为左子树和右子树的二叉树组成。特点：每个结点最多有两棵子树，即二叉树不存在度大于2的结点；二叉树的子树有左右之分，其子树的次序不能颠倒。

二叉树的五种形态：

斜树

有且仅有一个根节点，且子节点中都只包含左节点或者是右节点的称之为斜树，其实斜树本质上可以看作是链表的另一种形态。

满二叉树

满二叉树： 一个二叉树，如果每一层的结点数都达到最大值，则称这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是(2^k)-1，则它就是满二叉树。

完全二叉树

完全二叉树： 是效率很高的数据结构，它是由满二叉树而引出来的。对于深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。注意：满二叉树是一种特殊的完全二叉树。

二叉查找树-BST

二叉排序树（Binary Sort Tree），又称二叉查找树，亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

定义

二叉查找树为一颗空树或者是具有以下性质的二叉树：

1、如果左子树不为空，那么所有的左子树的节点值均小于根节点值。
2、如果右子树不为空，那么所有的右子树的节点值均大于根节点值。
3、以上两个性质对于除根节点外的所有的左右子树同样适用。即任意节点的左、右子树也分别为二叉查找树，同时没有键值相等的节点。

二叉查找树最大的优点是在于查找、插入的时间复杂度为O(logn)。二叉查找树是基础性的数据结构，用于构建更为抽象的数据结构，如集合，多重集，关联数组等。

查找

1、如果根节点的数据就是要查找的数据，则返回成功。
2、如果根节点的数据大于要查找的数据，则递归查找左子树。
3、如果根节点的数据小于要查找的数据，则递归查找右子树。
4、如果子树为空，则查找失败。

插入与删除

二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

平衡二叉树 - AVL

为什么要引入平衡二叉树

首先二叉查找树正常的插入和删除的时间复杂度为O(logn)，现在举一个比较特别的例子，如果插入的数据是{1,2,3，4}，这个时候的二叉查找树的形态可以这样子解读：

一旦遇到这种情况，二叉查找树的查询效率就变为O(n)，这使得效率大大降低了。

定义

平衡二叉搜索树被称之为AVL树，平衡二叉树可以定义为一颗空树，或者是一颗二叉查找树，在兼备二叉查找树的性质的同时又具有以下的几种特点：

1、平衡二叉树的形态之一是空树，另一种形态是树的左右节点的深度之差不可以超过1。
2、平衡二叉树除了根节点外的左右子树分别也是平衡二叉树，依次类推。
3、二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。

非平衡二叉树：

平衡二叉树：

红黑树 - RBT

红黑树（Red Black Tree） 是一种自平衡二叉查找树，也可以看作是一种特化的平衡二叉树(AVL)，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。红黑树不管是在最坏的情况下或者是最好的情况下，它的插入，查询，删除的时间复杂度都是O(logn)。

特点

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。除了二叉查找树的基本特性以外，红黑树还包含了以下几种特性：

1、红黑树的节点是红色或者是黑色。
2、红黑树的根节点是黑色。
3、红黑树的所有叶子都是黑色（叶结点即指树尾端NIL指针或NULL结点）。
4、在红黑树中，如果一个节点是红色，那么它的两个子节点都是黑色。
5、从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

红黑树示意图：

哈夫曼树

哈夫曼树被称之为最优二叉树，它是一种带权路径长度最短的二叉树，给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称之为哈夫曼树，在哈夫曼树中权值较大的结点离根较近。

基本术语

路径和路径长度： 在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
结点的权及带权路径长度： 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度： 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

第一步：拆散树的所有节点，并把所有节点看作是只有一个节点的树的集合。

第二步：选出权值最小的两颗树进行合并并且作为新树的左右节点，同时新树的根节点为左右子树的权值的和，在树的集合中删除这新树的左右节点，同时把新树添加进树的集合里面（选择权值为1和3的树）。

选择树的集合中最小的两个权值树（选择4和4）重复上述第二步的步骤：

选择权值6和7的树，重复步骤：

选择权值为8和8的树，重复步骤：

选择权值为10和13的树（有两个权值为13的，可以随便选择，为了方便我选择只有一个节点权值为13的树），重复步骤：

选择权值为13和14的树，重复步骤：

选择权值为16和13的树，重复步骤：

最后选择权值为29和23的树，重复步骤：

B树

B树（B-tree）是一种自平衡的树，能够保持数据有序，这种数据结构可以让查找数据，顺序访问，插入数据和删除数据等操作都在对数的时间内完成。

特点

B树概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

B树具有以下几种性质：

1、根节点至少有两个子女。
2、每个中间节点都包含k-1个元素和k个孩子。其中m/2<=k<=m
3、每个叶子节点都包含有k-1个元素，其中m/2<=k<=m。
4、所有的叶子节点都位于同一层。
5、每个节点中的元素从小到大排列，节点当中k-1个元素刚刚好是k个孩子包含的元素的值域划分。

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

B +树

B+ 树是一种树数据结构，通常用于关系型数据库(如Mysql)和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。

在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。 b+树的非叶子节点不保存数据，只保存子树的临界值(最大或者最小)，所以同样大小的节点，b+树相对于b树能够有更多的分支，使得这棵树更加矮胖，查询时做的IO操作次数也更少。

将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

R树

R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。 R树的核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外接矩形(MBR)，这个最小外接矩形就成为上一层的一个节点。因为所有节点都在它们的最小外接矩形中，所以跟某个矩形不相交的查询就一定跟这个矩形中的所有节点都不相交。叶子节点上的每个矩形都代表一个对象，节点都是对象的聚合，并且越往上层聚合的对象就越多。也可以把每一层看做是对数据集的近似，叶子节点层是最细粒度的近似，与数据集相似度100%，越往上层越粗糙。

![在这里插入图片描述](https://img-blog.csdnimg.cn/5e75ee6346ff49c0a5a066b21047579e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5reh5aKoQO-9nuaXoOeXlQ==,size_20,color_FFFFFF,t_70,g_
se,x_16)

总结

数组的下标寻址十分迅速，但计算机的内存是有限的，故数组的长度也是有限的，实际应用当中的数据往往十分庞大；而且无序数组的查找最坏情况需要遍历整个数组；后来人们提出了二分查找，二分查找要求数组的构造一定有序，二分法查找解决了普通数组查找复杂度过高的问题。任何一种数组无法解决的问题就是插入、删除操作比较复杂，因此，在一个增删查改比较频繁的数据结构中，数组不会被优先考虑。

普通链表 由于它的结构特点被证明根本不适合进行查找。

哈希表是数组和链表的折中，同时它的设计依赖散列函数的设计，数组不能无限长、链表也不适合查找，所以也适合大规模的查找。

二叉查找树因为可能退化成链表，同样不适合进行查找。

AVL树是为了解决可能退化成链表问题，但是AVL树的旋转过程非常麻烦，因此插入和删除很慢，也就是构建AVL树比较麻烦。

红黑树是平衡二叉树和AVL树的折中，因此是比较合适的。集合类中的Map、关联数组具有较高的查询效率，它们的底层实现就是红黑树。

多路查找树 是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的(如果元素数量非常多的话，查找就退化成节点内部的线性查找了)，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。

B树与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。它的应用是文件系统及部分非关系型数据库索引。

B+树在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。通常用于关系型数据库(如Mysql)和操作系统的文件系统中。

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针, 在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。

R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。

Trie树是自然语言处理中最常用的数据结构，很多字符串处理任务都会用到。Trie树本身是一种有限状态自动机，还有很多变体。什么模式匹配、正则表达式，都与这有关。

参考

• 数据结构图文解析之:树的简介及二叉排序树C++模板实现，https://www.it610.com/article/3607922.htm
• 各种二叉树的介绍https://www.cnblogs.com/aspirant/p/9019396.html
• 二叉树、二叉搜索树、平衡二叉树、B树、B+树的精确定义和区别探究https://www.cnblogs.com/williamjie/p/11081096.html
• 数据结构之树 https://blog.csdn.net/wannuoge4766/article/details/83998377
• B+Tree原理及mysql的索引分析https://www.cnblogs.com/xiaoxi/p/6894610.html
• https://blog.csdn.net/jarvan5/article/details/112428036
• 文章主要参考来源