对数时间查找

一般利用二叉搜索树来实现。

定义（二叉搜索树）

一个二叉树：任意节点满足： - 对于树中任意一个节点 \(x\)，\(x\) 左子树中任意节点 \(y\) 和 \(x\) 右子树中任意节点 \(z\)，这些节点存储的键值满足 \(y.key<x.key<z.key\)

明确定义后，其实二叉搜索树进行查找是显而易见的：如果查找 key 比 root 的小，就递归的在左子树查找。大则在右子树。等于则返回 root

而二叉搜索树的平衡性，对查找性能极为关键。下面讨论的红黑树就是一种常用的二叉搜索树。

红黑树

基本概念

• 染色：红黑树的每个节点要么是红色的，要么是黑色的
• 2-tree 结构：红黑树是一个 2-tree，每个节点要么有 2 个，要么有 0 个 child
• 二叉搜索树性质：红黑树首先是二叉搜索树。存储键值符合规律。
• 黑色高度： 定义 root 节点黑色深度为 0，。一个非根节点的黑色深度定义为从根节点到该节点的路径上黑色节点的个数（不包含根节点）。
  • 其实和传统高度定义类似，只是只考虑黑色节点

红黑树-递归定义

1. 唯一一个外部节点（也是 root）构成一个 black height 为 0 的红黑树 \(\mathrm{RB}_{0}\)
2. 对于 \(h\geq 1\)，一棵二叉树为准红黑树 \(\mathrm{ARB_{h}}\)，如果它的根节点为红色，且其左右子树均为 \(\mathrm{RB}_{h-1}\)
3. 对于 \(h\geq 1\)，一棵二叉树为红黑树 \(\mathrm{RB}_{h}\)，如果它的 root为黑色，且他的左右子树分别为一棵 \(\mathrm{RB}_{h-1}\) 或者 \(\mathrm{ARB}_{h}\) 容易验证，第 3 条结合第 2 条，保证 \(\mathrm{RB}_{h}\) 的黑色高度确实为 \(h\)