树

树的相关概念

• 树是满足以下任意定义的无向图：无环连通图不能闭环;具有 N 个节点和 N-l 条边的连通图;任意两个顶点都通过一条路径连接的图。
• 节点、根节点、父节点、子节点、叶子节点 (没有子节点的节点)、节点的权(节点值)、路径(从root节点找到该节点的路线)、层(根节点所在的位置为1层)、
• 子树:一棵完全包含在另一棵树中的树，它们通常用三角形表示，子树可能由单个节点组成！
• 树的高度(最大层数)
• 森林 :多颗子树构成森林

树的分类

• 二叉树（Binary Tree）每个节点最多有两个子节点。二叉树的子节点分为左节点和右节点
  • 完全二叉树：所有层都被完全填满，除了最后一层，节点尽可能靠左。
  • 满二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点
  • 平衡二叉树（Height-balanced Binary Tree）：任意节点的两个子树的高度差不超过1。
• 二叉搜索树（Binary Search Tree, BST）左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。它的左、右子树也分别为二叉排序树
  • 平衡二叉搜索树（BBST）：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    • AVL树（Adelson-Velsky and Landis Tree）：严格平衡的二叉搜索树，每个节点的左右子树高度差不超过1。
    • 红黑树（Red-Black Tree）：相对平衡的二叉搜索树，节点有颜色属性，通过红黑规则保持平衡。
    • Splay树（Splay Tree）：通过“伸展操作”将最近访问的节点旋转到根节点，优化后续访问。
    • Treap：结合了二叉搜索树和堆的性质，利用随机优先级保持平衡。
    • 重量平衡树（Weight Balanced Tree）：通过维护子树节点数量的比例保持平衡。
• B树（B-Tree）及其变种
  • B树（B-Tree）：一种自平衡的多路搜索树，广泛用于数据库和文件系统。
  • B+树（B+ Tree）：B树的变种，所有值存储在叶节点，并通过链表连接，便于区间查询。
  • B树（B Tree）：B+树的改进版本，插入和删除操作更高效。
  • 2-3树（2-3 Tree）：每个节点有两个或三个子节点，是B树的特例。
  • 2-3-4树（2-3-4 Tree）：每个节点有2到4个子节点的B树。
• 堆（Heap）
  • 二叉堆（Binary Heap）：一种完全二叉树，分为最大堆（根节点最大）和最小堆（根节点最小）。
  • 斐波那契堆（Fibonacci Heap）：支持更高效的合并操作。
  • 二项堆（Binomial Heap）：由二项树组成，支持高效的合并操作。
• 特殊树
  • Trie（前缀树或字典树）：用于高效存储和检索字符串集合。
  • 后缀树（Suffix Tree）：用于存储字符串的所有后缀，便于字符串模式匹配。
  • Segment Tree（线段树）：用于区间查询和更新。
  • Fenwick Tree（树状数组）：用于高效处理前缀和查询和更新操作。
  • K-D Tree：用于多维空间中的最近邻搜索。
  • Merkle Tree：用于区块链和数据完整性验证，叶节点存储数据块的哈希值。
  • R树（R-Tree）：用于多维空间中的区间查询和邻近查询。
  • Cartesian Tree：结合了堆和二叉搜索树的性质。
  • T树（T-Tree）：用于主存数据库系统的一种平衡树。
• 图和树的关系
  • 生成树（Spanning Tree）：包含图中所有节点且无环的子图。
  • 最小生成树（Minimum Spanning Tree, MST）：权重和最小的生成树。
  • 树图（Tree Graph）：无环连通图。
• 二叉树使用场景
  • 二叉搜索树 (BST)
  • 一些映射和集合的实现
  • 红黑树AVL 树Splay 树·等。
  • 二叉堆
  • 语法树（编译器和计算器使用）
  • Treap- 概率 DS（使用随机 BST）
• 二叉树复杂度
  操作 平均 最差
  insert O(log(n)) O(n)
  delete O(log(n)) O(n)
  remove O(log(n)) O(n)
  search O(log(n)) O(n)