数据结构—树
2024-04-10 10:15:47 7 举报AI智能生成
数据结构—树
作者其他创作
大纲/内容
什么是树
一种抽象的数据类型，具有树状结构性质的数据集合
树的重要概念
结点
树里面的元素
父子关系
结点之间相连的边
子树
结点大于一，其余互不相交节点的集合
度
一个结点拥有的字树的数量就是结点的度
叶子节点
度为0的节点
孩子
结点的子树的根称为孩子节点
双亲
和孩子结点对应
兄弟
同一个双亲的结点
深林
有多个互不相交的树组成深林
树形数据结构特性
结点高度
结点到叶子节点的最长路径
结点的深度
根节点到该结点的边的个数
结点的层数
结点的深度+1
树的高度
树的根结点的高度
二叉树
概念
二叉树是一种特殊的树形结构，每个结点最多只有两颗子树
二叉树的第N层最多有2^(N-1)次方个结点
满二叉树
除叶子结点外，其他结点都拥有左右两个结点
完全二叉树
除最后一层结点外，其他层结点个数必须达到最大，且最后一层的结点必须连续靠左排列
数组存储(数组下标i)
左结点=2*i
右结点=2*i+1
二叉树遍历(根节点输出)
前序遍历
根左右
中序遍历
左根右
后序遍历
左右根
层次遍历
队列实现
二叉搜索树
二叉搜索树定义
如果它的左子树不为空，则左子树上结点小于根结点
如果它的右子树不为空，则右子树结点大于根结点
特性
二叉搜索树的中序遍历是单调递增的
二叉搜索树的crud
插入： 每次插入结点时要从根结点开始比较，小的放左结点，大的放右结点
查找： 和插入的逻辑一致
二叉搜索树的删除
如果要删除的数是叶子结点，直接将叶子结点删除
如果要删除的结点只有一个子树，子树替换删除结点的位置
如果要删除的结点有左右两颗子树，找后继结点，而且后继结点的左子树一定为空
修改：查找到值修改
红黑树
什么是红黑树
红黑树是一颗自平衡二叉树，通过对红黑树插入、删除做特殊操作，保证红黑树的平衡特性。提高红黑树的查找性能（logn）
红黑树特性
红黑树有两种节点颜色：红色和黑色
根节点必须是黑色
红黑树的叶子结点是空的黑色结点，不存储任何数据
红黑树的结点不能是两个红色结点相连，且任意结点到达叶子结点的路径中，黑色结点的数量必须相等
红黑树新加入的点必须是红色
旋转和变色
变色
当前结点的父结点是红色，且它的祖父结点是的另一个子结点（叔叔结点）也是红色：
1. 把父结点设置为黑色
2. 把叔叔结点设置为黑色
3. 把祖父结点设置为红色
4. 把指针指向祖父结点
1. 把父结点设置为黑色
2. 把叔叔结点设置为黑色
3. 把祖父结点设置为红色
4. 把指针指向祖父结点
左旋
当前父结点是红色，叔叔结点是黑色，且当前结点是右子树。进行左旋操作（以父结点进行左旋）
右旋
当前父结点是红色，叔叔结点是黑色，且当前结点是左子树。变色+右旋
1. 把父结点变为黑色
2. 把祖父结点变为红色
3. 以祖父结点进行右旋
1. 把父结点变为黑色
2. 把祖父结点变为红色
3. 以祖父结点进行右旋
赫夫曼树（哈夫曼树）
什么是赫夫曼树
给定N个权值作为N个叶子结点的权重，构造一颗二叉树，如果该树所有带权路径长度之和最小，称这样的二叉树为最优二叉树，也称为赫夫曼树。注：权值越大离根结点越近
赫夫曼树与赫夫曼编码
赫夫曼树左子树所在边为二进制 0 ， 右子树所在边为 1。 从根结点到叶子结点的边组合起来就是该叶子结点的编码，称为 赫夫曼编码。
赫夫曼树的构建
构建赫夫曼树就是构建最优二叉树，使用贪心算法实现。
1. 将叶子结点集合按照权重从小到大排序
2. 取出两个最小的叶子结点，将两个叶子结点的权重相加，生成新的结点
3. 以新的结点为根，最小的两个结点为左右结点，建立新的子树
4. 将新结点放入排序集合中。
5. 重复上面4步，直到排序集合中只剩最后一个结点，哈夫曼树构建完成。
1. 将叶子结点集合按照权重从小到大排序
2. 取出两个最小的叶子结点，将两个叶子结点的权重相加，生成新的结点
3. 以新的结点为根，最小的两个结点为左右结点，建立新的子树
4. 将新结点放入排序集合中。
5. 重复上面4步，直到排序集合中只剩最后一个结点，哈夫曼树构建完成。
堆树
什么是堆树
堆树是一颗特殊的二叉树。
1. 首先它是一颗完全二叉树
2. 其每一个结点的值都大小等于左右子节点（大顶堆）或者小于等于左右子结点（小顶堆）
1. 首先它是一颗完全二叉树
2. 其每一个结点的值都大小等于左右子节点（大顶堆）或者小于等于左右子结点（小顶堆）
堆树示意图
堆树的插入删除(以数组A存储大顶堆为例)
插入
从下到上
1. 将期望结点插入到堆树的末尾，数组扩展一个位置。A[len] = 50
2. 插入结点和其父结点比较，如果 比父结点大交互位置，否则不用变
len = 2*i + 1
父结点位置pos = (len - 1) / 2
比较交换位置： A[pos] > A[len] ? 不动：交换位置
A[pos] = 50;
A[len] = 20;
len = pos;
父结点位置pos = (len - 1) / 2
比较交换位置： A[pos] > A[len] ? 不动：交换位置
A[pos] = 50;
A[len] = 20;
len = pos;
3. 交换后再与交换后的父结点比较，直到不能交换为止。
继续与父节点比较
len = 2*i + 1
父结点位置pos = (len - 1) / 2
比较交换位置： A[pos] > A[len] ? 不动：交换位置
A[pos] = 50;
A[len] = 40;
len = pos;
len = 2*i + 1
父结点位置pos = (len - 1) / 2
比较交换位置： A[pos] > A[len] ? 不动：交换位置
A[pos] = 50;
A[len] = 40;
len = pos;
从上到下
从上到下堆化过程与从下到上流程一致：
和当前结点的左右结点进行比较，如果比左右结点都大则不动。
否则和左右结点中较大的结点交换位置。
和当前结点的左右结点进行比较，如果比左右结点都大则不动。
否则和左右结点中较大的结点交换位置。
i = 0;
A[i] > A[2*i+1]; false
A[i] > A[2*i + 2]; false
A[i] = A[2*i + 1] > A[2*i + 2] ? A[2*i + 1] : A[2*i + 2]
i = 2*i+2 = 2
A[i] > A[2*i+1]; false
A[i] > A[2*i + 2]; false
A[i] = A[2*i + 1] > A[2*i + 2] ? A[2*i + 1] : A[2*i + 2]
i = 2*i+2 = 2
删除
将期望删除的结点和尾结点交换位置，删除尾结点。从期望删除的结点做从上到下的堆化。
堆排序（大顶堆）
构建堆树
左右子结点进行比较，如果比左右结点都大则不动。否则和左右结点中较大的结点交换位置
如果节点发生了交换，还需要对交换的节点进行堆化
倒数第一个结点做完堆化后，继续倒数第二个，直到达成任意子树满足堆树条件(根结点大于其左右结点)
排序
1. 将堆树的根结点和未做排序的最后一个结点交换位置，并做堆化，
2. 重复执行第一步，直到所有结点操作完成。最终堆树就会按照从小到大的顺序排序
2. 重复执行第一步，直到所有结点操作完成。最终堆树就会按照从小到大的顺序排序
B/B+ Tree
什么是B Tree？什么是B+ Tree?
B Tree 是一种高效的（logn）的平衡查找树，它的每个结点允许拥有多于两个子结点。B Tree的叶子结点都处于同一层，叶子结点不存储关键信息
B+ Tree 是B Tree的变种，主要区别在于 B + Tree的叶子结点存储了所有的关键信息，非叶子结点不存关键信息，保存指向下一层数据的索引。叶子结点之间用双向指针连接。可以说B+ Tree也是一颗B Tree。
B+ 树的特性
如果是一个m阶的B+树
每个结点最多有m个字结点
除根结点外，每个结点至少有 m/2 个子结点，向上取整 3 / 2 = 1.5 结点 = 2
根结点要么为空，要么只有根结点。否则 至少有2个字结点
有m个子结点就有m个关键码
叶子结点的高度一致
m=3 阶 B+ Tree 示意图
0 条评论
下一页
