数据结构—树

一种抽象的数据类型，具有树状结构性质的数据集合

树里面的元素

结点

结点之间相连的边

父子关系

结点大于一，其余互不相交节点的集合

子树

一个结点拥有的字树的数量就是结点的度

度

度为0的节点

叶子节点

结点的子树的根称为孩子节点

孩子

和孩子结点对应

双亲

同一个双亲的结点

兄弟

有多个互不相交的树组成深林

深林

树的重要概念

结点到叶子节点的最长路径

结点高度

根节点到该结点的边的个数

结点的深度

结点的深度+1

结点的层数

树的根结点的高度

树的高度

树形数据结构特性

什么是树

二叉树是一种特殊的树形结构，每个结点最多只有两颗子树

二叉树的第N层最多有2^(N-1)次方个结点

 概念

除叶子结点外，其他结点都拥有左右两个结点

满二叉树

除最后一层结点外，其他层结点个数必须达到最大，且最后一层的结点必须连续靠左排列

左结点=2*i

右结点=2*i+1

数组存储(数组下标i)

完全二叉树

根左右

前序遍历

左根右

中序遍历

左右根

后序遍历

队列实现

层次遍历

二叉树遍历(根节点输出)

二叉树

如果它的左子树不为空，则左子树上结点小于根结点

如果它的右子树不为空，则右子树结点大于根结点

二叉搜索树定义

二叉搜索树的中序遍历是单调递增的

特性

插入： 每次插入结点时要从根结点开始比较，小的放左结点，大的放右结点

查找： 和插入的逻辑一致

如果要删除的数是叶子结点，直接将叶子结点删除

如果要删除的结点只有一个子树，子树替换删除结点的位置

如果要删除的结点有左右两颗子树，找后继结点，而且后继结点的左子树一定为空

二叉搜索树的删除 

修改：查找到值修改

二叉搜索树的crud

二叉搜索树

红黑树是一颗自平衡二叉树，通过对红黑树插入、删除做特殊操作，保证红黑树的平衡特性。提高红黑树的查找性能（logn）

什么是红黑树

红黑树有两种节点颜色：红色和黑色

根节点必须是黑色

红黑树的叶子结点是空的黑色结点，不存储任何数据

红黑树的结点不能是两个红色结点相连，且任意结点到达叶子结点的路径中，黑色结点的数量必须相等

红黑树新加入的点必须是红色

红黑树特性

当前结点的父结点是红色，且它的祖父结点是的另一个子结点（叔叔结点）也是红色：1. 把父结点设置为黑色2. 把叔叔结点设置为黑色3. 把祖父结点设置为红色4. 把指针指向祖父结点

变色

当前父结点是红色，叔叔结点是黑色，且当前结点是右子树。进行左旋操作（以父结点进行左旋）

左旋

当前父结点是红色，叔叔结点是黑色，且当前结点是左子树。变色+右旋1. 把父结点变为黑色2. 把祖父结点变为红色3. 以祖父结点进行右旋

右旋

旋转和变色

红黑树

给定N个权值作为N个叶子结点的权重，构造一颗二叉树，如果该树所有带权路径长度之和最小，称这样的二叉树为最优二叉树，也称为赫夫曼树。注：权值越大离根结点越近

什么是赫夫曼树

赫夫曼树左子树所在边为二进制 0 ， 右子树所在边为 1。 从根结点到叶子结点的边组合起来就是该叶子结点的编码，称为 赫夫曼编码。

赫夫曼树与赫夫曼编码

构建赫夫曼树就是构建最优二叉树，使用贪心算法实现。1. 将叶子结点集合按照权重从小到大排序2. 取出两个最小的叶子结点，将两个叶子结点的权重相加，生成新的结点3. 以新的结点为根，最小的两个结点为左右结点，建立新的子树4. 将新结点放入排序集合中。5. 重复上面4步，直到排序集合中只剩最后一个结点，哈夫曼树构建完成。

赫夫曼树的构建

赫夫曼树（哈夫曼树）

堆树是一颗特殊的二叉树。1. 首先它是一颗完全二叉树2. 其每一个结点的值都大小等于左右子节点（大顶堆）或者小于等于左右子结点（小顶堆）

堆树示意图

什么是堆树

1. 将期望结点插入到堆树的末尾，数组扩展一个位置。A[len] = 50

len = 2*i + 1 父结点位置pos = (len - 1) / 2比较交换位置： A[pos] > A[len] ? 不动：交换位置A[pos] = 50;A[len] = 20;len = pos;

2. 插入结点和其父结点比较，如果 比父结点大交互位置，否则不用变

继续与父节点比较len = 2*i + 1父结点位置pos = (len - 1) / 2比较交换位置： A[pos] > A[len] ? 不动：交换位置A[pos] = 50;A[len] = 40;len = pos;

3. 交换后再与交换后的父结点比较，直到不能交换为止。

从下到上

i = 0;A[i] > A[2*i+1]; falseA[i] > A[2*i + 2]; falseA[i] =  A[2*i + 1] > A[2*i + 2] ? A[2*i + 1] : A[2*i + 2]i = 2*i+2 = 2

从上到下堆化过程与从下到上流程一致：和当前结点的左右结点进行比较，如果比左右结点都大则不动。否则和左右结点中较大的结点交换位置。

从上到下

插入

将期望删除的结点和尾结点交换位置，删除尾结点。从期望删除的结点做从上到下的堆化。

删除

堆树的插入删除(以数组A存储大顶堆为例)

左右子结点进行比较，如果比左右结点都大则不动。否则和左右结点中较大的结点交换位置

如果节点发生了交换，还需要对交换的节点进行堆化

倒数第一个结点做完堆化后，继续倒数第二个，直到达成任意子树满足堆树条件(根结点大于其左右结点)

构建堆树

1. 将堆树的根结点和未做排序的最后一个结点交换位置，并做堆化，2. 重复执行第一步，直到所有结点操作完成。最终堆树就会按照从小到大的顺序排序

排序

堆排序（大顶堆）

堆树

B Tree 是一种高效的（logn）的平衡查找树，它的每个结点允许拥有多于两个子结点。B Tree的叶子结点都处于同一层，叶子结点不存储关键信息

B+ Tree 是B Tree的变种，主要区别在于 B + Tree的叶子结点存储了所有的关键信息，非叶子结点不存关键信息，保存指向下一层数据的索引。叶子结点之间用双向指针连接。可以说B+ Tree也是一颗B Tree。

什么是B Tree？什么是B+ Tree?

每个结点最多有m个字结点

除根结点外，每个结点至少有 m/2 个子结点，向上取整 3 / 2 = 1.5   结点 = 2

根结点要么为空，要么只有根结点。否则 至少有2个字结点

有m个子结点就有m个关键码

叶子结点的高度一致

如果是一个m阶的B+树

m=3 阶 B+ Tree 示意图

B+ 树的特性

B/B+ Tree

树