3、树

定义

树是种非线性存储结构，存储着一对多关系的数据元素的集合。

其结构类似于倒着的树，故称为“树形”存储结构。

节点

定义：每一个数据元素被称为节点。
节点的上级节点为该节点的父节点，该节点也叫父节点的子节点，而具有相同父节点的节点就叫做兄弟节点，如果一个节点没有父节点，则该节点即为树的根节点，如果节点没有子节点，则叫做叶节点。

子树与空树

子树：一个树包含在其他树中时，则被称为子树。
空树：一个树中没有任何集合，则叫做空树。

节点的度和层次

度：对一个节点，拥有的子节点个数，则称为节点的度。
层次：层次即从根节点开始算，该节点所在的层数。一棵树的深度（高度）即树中节点的最大层次。

树的表示方法

除了常规的表示，树还有其他的表示方式：

分别为嵌套的集合与凹入表示法。
最常用的使用广义表：(A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )。

树的分类图

二叉树

定义：树的任意节点最多包含两个子节点。
常用的二叉树：满二叉树、完全二叉树、平衡二叉树（AVL）、二叉查找树（二叉搜索树、BST）、

满二叉树

定义：除最后一层无节点，剩下的每一层节点都有两个子节点。
性质：

• 若层数为k，则节点总数为（2^k）-1，故节点数一定是奇数个；
• 第i层上的节点数为：2^(i-1)；
• 若层数为k，叶子节点数为：2^(k-1)；

完全二叉树

定义：如果对满二叉树节点进行编号，顺序为根节点开始，自上而下，自左而右，则深度为k，节点数为n的二叉树，当且仅当每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应，称为完全二叉树。意思是完全二叉树比满二叉树少的节点，只能从右向左，从下到上的顺序。

性质：

• 最后一层节点数
• 左子树的节点数：
  
• 右子树的节点数：
  
• 堆一般都是用完全二叉树来实现的。

二叉搜索树

定义：又叫二叉排序树，简单来说就是左子树上的所有节点的值都小于根节点的值，右子树上节点的值都大于根节点的值，并且左节点小于父节点的值，右节点大于父节点的值。

性质：

• 左小右大
• 没有键值相等的节点

平衡二叉树（AVL树）

定义：在二叉排序树基础上发展而来的，它左右子树的高度差的绝对值不超过1，并且左右两颗子树都是一颗平衡二叉树。其很好的解决了二叉查找树退化为链表的问题，相对于二叉查找树，插入与删除的时间上稳定了很多。
性质：

• 它是一颗空树或者左右两个子树的高度差绝对值不超过1；
• 左右子树也是一颗平衡二叉树；

旋转：
平衡二叉树节点失衡，可以通过旋转的方式调节。
（1）左左

左子树的左节点（1），造成二叉树失衡，根节点高度绝对值超过了1，故将（3）作为根节点，即可平衡。
（2）右右

右子树的右节点（5），造成二叉树失衡，根节点高度绝对值超过1，故将（3）作为根节点，即可平衡。
（3）左右

左子树的右节点（3），造成二叉树失衡，节点（5）高度差绝对值超过1，故先通过右右情况调节，再通过左左情况调节，即可平衡。
（4）右左

右子树的左节点（18），造成二叉树失衡，节点（15）高度差绝对值超过1，故先通过左左情况调节，再通过右右情况调节，即可平衡。

红黑树

定义：红黑树是一种自平衡二叉查找树，典型的用途是实现关联数组。
性质：

• 任一子树都是红黑树；
• 节点是红色或黑色；
• 根节点与叶子节点（在java中，叶子节点为null节点）都是黑色；
• 每个红色节点的两个子节点都是黑色；
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树查找

红黑树资料链接网站
https://www.jianshu.com/p/e136ec79235c

哈夫曼树

定义：给定N个权值作为N个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，则称为最优二叉树，也叫哈夫曼树，其权值较大的离根较近。
概念基础：
（1）路径：在一棵树中，从一个节点到另一个节点经过的所有节点，称为两个节点之间的路径。

从A到H的路径：A-B-D-H。
（2）路径长度：从一个节点到另一个节点所经过的“边”的数量，被称为两个节点之间的路径长度。

从A到H的路径长度：3。
（3）节点的带权路径长度：路径长度 * 该节点的权重

故H节点的带权路径长度=3 * 3=9。
（4）树的带权路径长度：所有叶子节点的带权路径长度之和，也简称为WPL。

故此二叉树的路径长度为：9+18+2+8+16=53

哈夫曼编码：

定义：是可变字长编码（VLC）的一种，其方法依据字符出现概率来构造异字头的平均长度最短的码字，有时也称为最佳编码。
目的：根据使用频率来最大化节省字符（编码）的存储空间。
方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。
图解：

二叉树的遍历

前序遍历：根左右
中序遍历：左根右
后序遍历：右根左

B树

B-树

定义：B-树也就是B树，又叫平衡多路查找树，是为了存储设备或磁盘而设计的一种平衡查找树。
特性：

• 树中的每个结点最多含有m个孩子；
• 除了根结点和叶子结点，其他结点至少有[ceil(m / 2)（代表是取上限的函数）]个孩子；
• 若根结点不是叶子结点时，则至少有两个孩子（除了没有孩子的根结点）
• 所有的叶子结点都出现在同一层中，叶子结点不包含任何关键字信息；

B树的阶：
B树中的一个节点的子节点数目的最大值，用m表示。

所有节点中，[13,16,19]拥有最多的四个子节点，故可定义其为4阶B数。
根节点：没有父节点的节点称为根节点。
内部节点：拥有父节点和子节点的节点。
叶子节点：只拥有父节点，没有子节点的节点。

B+树

定义：B+树可以说是B树的一种变形，把数据存储在叶节点，而内部节点只存储关键字和孩子指针，因此简化了内部节点的分支因子。

优点：B+树比B树更适合做操作系统的数据库索引和文件索引。

• B+树的磁盘读写代价更低，因为其内部节点没有指向关键字具体信息的指针。
• B+树的查询更加稳定，因为非终节点并不是最终指向文件内容的节点，仅仅作为叶子节点中关键字的索引。所有关键字查询长度都是相同的，查询效率相当。
• B+树便于范围查询，B+树只需要遍历叶子节点就可实现整棵树的遍历。B树的范围查找用的是中序遍历，而B+树是在链表上遍历。

B*树

定义： B* 树是B+树的变体，在B+树的非根和非叶子节点增加指向兄弟的指针，B* 树定义了非叶子节点关键字个数至少为（2/3）* M,即每块的最低使用率为2/3。
优点： B* 树分配新节点的概率比B+树要低。