引言
动机：我们希望寻找一种数据结构来存储元素，它能够提供高效的、任意位置的检索（查找）、插入和删除操作。
- 基于数组的列表 (Array-based Lists)
- 插入和删除操作的时间复杂度为 $O(n)$
- 基于索引的检索速度很快
- 如果已排序，可以使用高效的二分查找
- 链表 (Linked Lists)
- 在头部/尾部进行插入/删除操作非常高效，时间复杂度为 $O(1)$
- 任意位置的查找/插入/删除操作效率较低，时间复杂度为 $O(n)$
- 由于缺乏随机访问能力，无法进行高效的二分查找
- 栈 (Stacks) 和队列 (Queues) 虽然操作高效，但属于受限访问的数据结构
- 可能的替代方案：树 (Trees)
- 树结构具有为所有操作提供 $O(\log n)$ 高效性的潜力。
定义与术语
- • 在图论中，树 (tree) 是一个无环图。
- 在本文的语境中，树是节点 (nodes) 的集合（这些节点可以包含键、数据等），它们通过边 (edges) 连接。
- 树也是有向的 (oriented)：每个节点都有一个父节点 (parent) 和若干个子节点 (children)。
- 没有父节点的节点称为树的根 (root)，所有子节点都向下排列。
- 没有直接连接的节点之间可以具有祖先 (ancestor)、后代 (descendant) 或堂兄弟 (cousin) 关系。
- 没有子节点的节点称为叶子 (leaf)。
- 所有节点最多有两个子节点的树称为二叉树 (binary tree)。
- 二叉树在水平方向上也是有向的：每个节点可能有一个左子节点 (left child) 和/或一个右子节点 (right child)。
- 示例：
特性：
在树中，所有节点都通过唯一的一条路径相连。
在二叉树中，第 $k$ 层（根节点为第 0 层）的最大节点数为 $2^k$。
因此，深度为 $d$ 的任意二叉树的最大节点数 $n$ 为：
$$
n = 2^0 + 2^1 + 2^2 + \dots + 2^{d-1} + 2^d = \sum_{k=0}^d 2^k = 2^{d+1} - 1
$$对于一个含有 $n$ 个节点的满二叉树 (full binary tree)，其深度为：
$$
d = \log(n+1) - 1
$$即，$d = O(\log n)$。
动机总结：如果我们能够创建一个基于树的数据结构，其操作耗时与树的深度成正比，那么我们就有可能得到一个允许在 $O(\log n)$ 时间内进行检索/查找、插入和删除的数据结构。