树有多种多样,本文偏重概览介绍,不做展开。

简单定义

二叉树

二叉树(Binary Tree)是每个结点最多有 2 个子树的树结构,分支一般分左右,不能颠倒。

二叉树的一些相关定义如下:

  • (Level):从根结点开始,一般认为根为第 1 层;
  • 深度(Depth):从根到某个结点的路径长,一般认为根的深度为 0;
  • 高度(Height):从某个结点到叶结点的最长路径,叶结点的高度为 0;

根据以上定义,二叉树的第 $i$ 层最多拥有 $2^{i-1}$ 个结点($i$ 从 1 开始)。深度为 $k$ 的二叉树最多有 $2^{k+1}-1$ 个结点。

二叉树的拓展

完全二叉树

完全二叉树(Complete Binary Tree)指的是除了最后一层之外所有层的结点数目全满、且最后一层的结点都集中在该层最左边的二叉树。

满二叉树

满二叉树(Full Binary Tree)指的是所有叶结点都在最后一层的 完全二叉树

二叉查找树(BST)

二叉查找树(Binary Search Tree,BST)指一棵空树、或具有下列性质的二叉树:

  • 任意结点的左、右子树也为 BST;
  • 任意结点的左子树上所有结点的值均小于该结点的值,右子树上所有结点的值均大于该结点的值;
  • 没有键值相等的结点。

由于 BST 蕴含了结点之间的大小关系,因此非常便于储存有顺序的数据,其查找、插入、删除的时间复杂度期望平均为 $O(\log n)$,最坏为 $O(n)$。

平衡二叉树

平衡二叉树(Self-balancing Binary Search Tree)指一棵空树、或具有下列性质的 BST

  • 任意结点的左、右子树也为平衡二叉树;
  • 任意结点的左右两个子树的高度差不超过 1。

AVL 树

TODO

红黑树

  • 红黑树(Red–black Tree)[ref]

B 树

  • B 树(B-tree)[ref]
    • 一种多路 平衡查找树,每个结点最多包含 m 个子结点,m 被称为 B 树的 ,B 树具有以下性质:
      • B 树只有 1 个结点,或根结点至少有 2 个子结点
      • 若中间结点有 k 个子结点,那么包含的键值个数为 k-1 个,k-1 个键值刚好是 k 个子结点包含的键值的值域分划
      • 所有结点的 子结点数量 k(若为内部结点)与 键值数量 k-1 满足 ceil(m/2) <= k <= m
      • 所有结点的键值都 从小到大 排列
      • 所有的 叶结点 都位于同一层
    • 当数据被插入或从一个结点中移除,它的子结点数量发生变化。为了维持在预先设定的数量范围内,内部结点可能会被 合并分离。由于子结点数量有一定的允许范围,所以 B 树不需要像其他自平衡查找树那样频繁地重新保持平衡,但是由于结点没有被完全填充,可能浪费了一些空间。子结点数量的上界和下界依特定的实现而设置。
    • 为大块数据的读写操作做了优化,通过减少定位记录时所经历的中间过程,从而加快存取速度。因此可用来描述外部存储,常被应用在数据库和文件系统的实现上
  • 2-3 树(2–3 Tree,3 阶 B 树)[ref]
    • 查找效率与树的高度息息相关
      • 最坏情况 下所有的结点都是 2-node 结点,查找效率为 log n
      • 最好情况 下所有的结点都是 3-node 结点,查找效率为 log_3 n,约等于 0.631 log n
  • B+ 树(B+ Tree)
  • B* 树(B* Tree)

其他

  • 遍历(Traversal)
    • 深度优先
      • 前序(Pre-order):根结点 -> 左子树 -> 右子树
      • 中序(In-order):左子树 -> 根结点 -> 右子树
      • 后序(Post-order):左子树 -> 右子树 -> 根结点
    • 广度优先
  • 需要的功能:插入、删除、构建、查找、遍历等

参考