考研数学必会树算法速记

这是一篇关于考研数学必会树算法速记的思维导图，主要内容包括：树的定义和基本概念，树的性质，二叉树，二叉搜索树（BST），平衡二叉树（AVL树），堆和优先队列，哈夫曼树（Huffman Tree），红黑树，B树和B 树，树算法的应用。

考研数学必会树算法速记

• 树的定义和基本概念
  • 树的定义
    • 由n个有限节点组成
    • 有且仅有一个根节点
    • 其余节点分为m个互不相交的有限集
  • 节点的度
    • 节点拥有的子树数
  • 树的度
    • 树中节点的最大度数
  • 叶子节点
    • 度为0的节点
  • 分支节点
    • 度不为0的节点
• 树的性质
  • 树中节点数等于边数加1
  • 具有n个节点的完全二叉树深度为log2(n+1)
  • 具有n个节点的完全二叉树，如果按层次从上到下、从左到右编号，则编号为i的节点的左子节点编号为2i，右子节点编号为2i+1
• 二叉树
  • 二叉树的定义
    • 每个节点最多有两个子节点的树结构
  • 满二叉树
    • 每一层的节点数都达到最大值
  • 完全二叉树
    • 除了最后一层外，其他各层的节点数都达到最大值，且最后一层的节点都靠左排列
  • 二叉树的遍历
    • 前序遍历
      • 先访问根节点，再前序遍历左子树，最后前序遍历右子树
    • 中序遍历
      • 先中序遍历左子树，再访问根节点，最后中序遍历右子树
    • 后序遍历
      • 先后序遍历左子树，再后序遍历右子树，最后访问根节点
    • 层序遍历
      • 按层次从上到下、从左到右访问所有节点
• 二叉搜索树（BST）
  • 二叉搜索树的定义
    • 左子树上所有节点的值均小于它的根节点的值
    • 右子树上所有节点的值均大于它的根节点的值
    • 左右子树也分别为二叉搜索树
  • 二叉搜索树的性质
    • 中序遍历结果为递增序列
  • 二叉搜索树的操作
    • 查找
      • 从根节点开始，若目标值小于节点值则往左子树查找，大于则往右子树查找，直到找到目标值或叶子节点
    • 插入
      • 类似查找过程，直到找到一个空位置插入新节点
    • 删除
      • 删除节点分为三种情况：无子节点、一个子节点、两个子节点
• 平衡二叉树（AVL树）
  • 平衡二叉树的定义
    • 任何节点的两个子树的高度最大差别为1
  • 平衡二叉树的旋转
    • 单旋转
      • LL旋转：右旋转
      • RR旋转：左旋转
    • 双旋转
      • LR旋转：先左后右旋转
      • RL旋转：先右后左旋转
  • 平衡二叉树的调整
    • 在插入或删除节点后，若树不平衡，通过旋转操作恢复平衡
• 堆和优先队列
  • 堆的定义
    • 一种特殊的完全二叉树
    • 满足父节点的值总是大于或等于（大顶堆）或小于或等于（小顶堆）任何一个子节点的值
  • 堆的操作
    • 插入
      • 将新元素添加到堆的末尾，然后通过上浮操作调整堆
    • 删除
      • 删除堆顶元素，然后用堆的最后一个元素替换它，通过下沉操作调整堆
    • 构建堆
      • 从最后一个非叶子节点开始，通过下沉操作构建堆
  • 优先队列
    • 一种抽象数据类型，允许插入元素并删除具有最高优先级的元素
    • 通常使用堆来实现优先队列
• 哈夫曼树（Huffman Tree）
  • 哈夫曼树的定义
    • 带权路径长度最短的二叉树，权值为叶子节点的权值
  • 哈夫曼编码
    • 基于哈夫曼树的最优前缀编码方法
    • 频率高的字符使用较短的编码，频率低的字符使用较长的编码
  • 哈夫曼树的构建
    • 将所有节点视为单节点树，权值为节点的权值
    • 将权值最小的两棵树合并为一棵新树，新树的根节点权值为两棵树根节点权值之和
    • 重复上述步骤，直到只剩下一棵树，即为哈夫曼树
• 红黑树
  • 红黑树的定义
    • 一种自平衡的二叉搜索树
    • 每个节点都有一个颜色属性，可以是红色或黑色
  • 红黑树的性质
    • 根节点是黑色
    • 所有叶子节点（NIL节点，空节点）是黑色
    • 红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
    • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
    • 新插入的节点默认为红色
  • 红黑树的旋转和重新着色
    • 插入和删除节点后，通过旋转和重新着色来保持红黑树的性质
• B树和B+树
  • B树的定义
    • 一种平衡的多路搜索树
    • 每个节点可以有多个子节点，通常用于数据库和文件系统
  • B树的性质
    • 所有叶子节点都在同一层
    • 非根节点的节点数n满足：t-1 ≤ n ≤ 2t-1，其中t是树的最小度数
    • 每个节点的关键字数n满足：t-1 ≤ n ≤ 2t-1
    • 所有关键字都按照顺序排列
  • B+树的定义
    • B树的一种变体
    • 所有数据记录都存放在叶子节点
    • 非叶子节点仅用于索引，包含指向子节点的指针和关键字
  • B+树的特点
    • 叶子节点之间通过指针连接，便于顺序遍历
    • 非叶子节点的冗余度更高，使得树更加平衡，提高查询效率
• 树算法的应用
  • 排序和搜索
    • 二叉搜索树可用于快速查找、插入和删除操作
  • 数据压缩
    • 哈夫曼编码用于数据压缩算法中
  • 数据库索引
    • B树和B+树广泛用于数据库索引结构
  • 优先级调度
    • 优先队列用于操作系统中的任务调度算法
  • 文件系统
    • B树和B+树用于文件系统的磁盘存储管理