常用树的简要介绍 – 恶补基础系列

前言
树的定义和基本术语
二叉树
B树
B+树
参考文章

前言

继续补基础啊。。。。数据结构内容，一般不会涉及代码，只会介绍实现思路。

树作为一种数据结构，虽然经常在用，但是从来没仔细研究过，简直是罪过罪过。

还有，我一直搞不清到底节点，还是结点；书上用结点，但是个人习惯打节点。如果用混了，就当没看见。。

树的定义和基本术语

树型结构是一类重要的非线性数据结构，以分支关系定义层次结构。树的定义如下：

树是 n( n≥0 ) 个结点的有限集。任意一颗非空树中：

有且只有一个特定得称为根（Root）的结点

当 n > 1 时，其余结点可分 m( m>0 ) 个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)

明显，这里是一个递归的概念。

结点：树的每个元素成为结点（node），结点是树的一个独立单元。
空树：结点 n==0，结点为0。
树的度 ：结点拥有的子树的数量为结点的度，度为0的结点是叶结点，度不为0的结点为分支结点，树的度定义为树的所有结点中度的最大值。
叶子：度为 0 的结点称为叶子或终端结点。
树的前驱和后继 ：结点的直接后继称为结点的孩子，结点称为孩子的双亲。结点的孩子的孩子称为结点的孙子，结点称为子孙的祖先。同一个双亲的孩子之间互称兄弟。
双亲和孩子 ：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
兄弟：同一个双亲的孩子之间互称兄弟。
祖先：从根到该结点所经分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。
树的深度 ：树中结点的最大层次称为树的深度或高度。
有序树和无序树 ：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林：是 m (m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。

二叉树

二叉树 (Binary Tree) 是 n(n≥0) 个结点所构成的集合，对于非空树T:

有且仅有一个称之为根的结点；
除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）；
二叉树的子树有左右之分，其次序不能任意颠倒

二叉树的性质：

在二叉树的第 i 层上至多有 2^( i – 1 ) 个结点（ i ≥ 1 )
深度为 K 的二叉树至多有 2^k -1个结点 ( k ≥ 1 )
对任何一棵二叉树 T ，如果其终端结点数为 n，度为2的结点数为 m，则 n = m +1
任意一棵树，结点数等于分支数加一

二叉树的遍历：

前序遍历：对于所有节点，访问顺序遵循：父节点->左子树->右子树的逻辑
中序遍历：和前序遍历的区别是遍历顺序改为左子树->父节点->右子树
后序遍历：对于所有节点，顺序为左子树->右子树->根节点
层序遍历：将二叉树看作一栋楼，每层有不同数目的房间，按照从上到下、从左到右的顺序依次访问节点。实现程序不再使用递归，而是使用了“先进先出”的queue容器。

二叉树最常用的存储结构是链式结构；顺序存储更适用于完全二叉树，在堆排序时有奇效。

满二叉树

深度为 K 且含有 2^k -1个结点的二叉树。每一层上的结点都是最大结点数。

简单点说，就是每一层都是放满的。

完全二叉树

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

堆就是一个完全二叉树，构建结构为从上到下，从左到右。。

堆的下标关系：

根节点下标为0
若节点 P 的下标为 i，则左孩子为 2i+1，右孩子为 2i+2
若节点 P 的下标为 i，则父节点的下标为 (i-1)/2

二叉排序树

二叉排序树（Binary Sort Tree，简称为 BST）又称二叉查找树、二叉搜索树。它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有相等的键值；

BST 的插入判断步骤：

若为空树，则将 X 作为根节点；

若不为空树，且 X 小于 BST 的根节点值，则将 X 插入左子树；

若不为空树，且 X 大于 BST 的根节点值，则将 X 插入右子树。

因为 BST 具有上述特点，所以具有有一个性质：BST的中序遍历结果即是其所有节点值从小到大的排序结果。

BST 构建和插入的顺序有很大关系。

随便放了几个数字，可以参照图比较一下以上性质。

BST 的查找顺序：

如果当前节点为空，则返回空；

如果 X 等于当前节点的值，则返回该节点；

如果 X 大于当前节点的值，则去该节点的右子树查找；

X 小于当前节点的值，则去该节点的左子树查找。

BST 最大值在最右侧，最小值在最左侧。

平衡二叉排序树

平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

平衡二叉排序树，又成为 AVL树 ，平衡二叉树是基于二叉查找树的改进。

由于在某些极端的情况下（如在插入的序列是有序的时），二叉排序树将退化成近似链，此时，其操作的时间复杂度将退化成线性的，即 O(n)。所以我们通过自平衡操作（即旋转）构建两个子树高度差不超过1的平衡二叉树。

以下部分节选自，更具体请参考原文：https://blog.csdn.net/weixin_36888577/article/details/87211314

平衡因子 : 树中某结点其左子树的高度和右子树的高度之差。
AVL 树中的任意一个结点, 其平衡因子的绝对值小于2
AVL 树是一种特殊的二叉搜索树 (BST树), 相对于数据极端情况下, 二叉搜索树会退化成为单链表, AVL 树定义了旋转操作, 在平衡因子大于等于2时, AVL 树会旋转来调整树的结构, 来重新满足平衡因子小于2。

哈夫曼树

哈夫曼( Huffman )树又称最优树，是一类带权路径长度最短的树。

比较详细的哈夫曼树介绍可以阅读：https://zhuanlan.zhihu.com/p/53645510

大概的思路就是：选出最小的，然后相加，再循环。

红黑树

红黑树也是一种自平衡的二叉排序树。

红黑树是每个节点都带有颜色属性的二叉排序树，颜色为红色或黑色。在二叉排序树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些约束确保了红黑树的关键特性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉排序树。

B树

B树和B+树的介绍可以参考：

B树也是一种用于查找的平衡树，但是它不是二叉树。

B树的定义： B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

B树作为一种多路搜索树（并不是二叉的）：

1) 定义任意非叶子结点最多只有M个儿子；且M>2；

2) 根结点的儿子数为[2, M]；

3) 除根结点以外的非叶子结点的儿子数为[M/2, M]；

4) 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5) 非叶子结点的关键字个数=指向儿子的指针个数-1；

6) 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7) 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

8) 所有叶子结点位于同一层；

如下图为一个M=3的B树示例：