搜索树

二叉搜索树 BST

满足以下特性的二叉树是棵二叉搜索树（Binary Search Tree）：

1. 每个元素有一个关键字，并且任意两个元素的关键字都不同；因此所有关键字都是唯一的；
2. 在根节点的左子树中，元素的关键字（如果有的话）都小于根节点的关键字；
3. 在根节点的右子树中，元素的关键字（如果有的话）都大于根节点的关键字；
4. 根节点的左右子树也都是二叉搜索树。

AVL 搜索树

AVL 树是 Adelson-Velskii 和 Landis 在 1962 年提出的：

1. AVL 搜索树是一棵二叉搜索树
2. 左右子树的高分别为 $$h_L, h_R$$，则 AVL 搜索树有：$$|h_L - h_R| \le 1$$
3. AVL 搜索树根节点的左子树和右子树也是 AVL 搜索树。

红黑树

红黑树：

1. 红黑树是一个带有颜色的二叉查找树，所有结点均是红色或黑色；
2. 根是黑色；
3. 所有叶子都是黑色（叶子结点是外部结点）；
4. 每个红色结点必须有两个黑色结点；
5. 从任一节点到其每个叶子的简单路径都包含相同数量的黑色结点。

B-树

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

1. 每个节点最多有 m 个子节点；
2. 每个非叶子节点（除根节点）最少有 $$\displaystyle [\frac{m}{2}] $$ 个子节点；
3. 如果根节点不是叶子节点，那么它至少有两个子节点；
4. 有 k 个子节点的非叶子节点拥有 k − 1 个键；
5. 所有的叶子节点都在同一层。