查找表

一般对于查找表有以下几种操作：

在查找表中查找某个具体的数据元素；
在查找表中插入数据元素；
从查找表中删除数据元素；

在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。

二分查找

使用的前提是静态查找表中的数据必须是有序的。

折半查找的运行过程可以用二叉树来描述，这棵树通常称为“判定树”。

折半查找的平均查找长度为：ASL = log2(n+1) – 1。

折半查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。

二叉排序树（二叉查找树）

动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。

具有如下特点：

二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
二叉排序树的左右子树也要求都是二叉排序树；

一个无序序列可以通过构建一棵二叉排序树，从而变成一个有序序列。当使用中序遍历算法遍历二叉排序树时，得到的序列为有序序列。

使用二叉排序树实现动态查找操作的过程，实际上就是从二叉排序树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。

平衡二叉树（AVL树）

遵循以下两个特点的二叉树：

每棵子树中的左子树和右子树的深度差不能超过 1；
二叉树中每棵子树都要求是平衡二叉树；

平衡因子：每个结点都有其各自的平衡因子，表示的就是其左子树深度同右子树深度的差。取值只可能是：0、1 和 -1。

使用平衡二叉树进行查找操作的时间复杂度为 O(logn)。

红黑树

两个要求：

树中的每个结点增加了一个用于存储颜色的标志域；
树中没有一条路径比其他任何路径长出两倍，整棵树要接近于“平衡”的状态。

满足以下性质的二叉查找树才是红黑树：

树中的每个结点颜色不是红的，就是黑的；
根结点的颜色是黑的；
所有为 nil 的叶子结点的颜色是黑的；（注意：叶子结点说的只是为空（nil 或 NULL）的叶子结点！）
如果此结点是红的，那么它的两个孩子结点全部都是黑的；
对于每个结点，从该结点到到该结点的所有子孙结点的所有路径上包含有相同数目的黑结点；

每个结点附带一个整形数值，表示的是此结点的黑高度（从该结点到其子孙结点中包含的黑结点数，用 bh(x) 表示（x 表示此结点）），nil 的黑高度为 0，颜色为黑色。

整棵树也有自己的黑高度，即为根结点的黑高度。对于一棵具有 n 个结点的红黑树，树的高度至多为：2lg(n+1)。

红黑树进行查找操作时的时间复杂度为O(lgn)

B-树

一颗 m 阶的 B-树，或者本身是空树，否则必须满足以下特性：

树中每个结点至多有 m 棵子树；
若根结点不是叶子结点，则至少有两棵子树；
除根之外的所有非终端结点至少有 ⌈m/2⌉ 棵子树；
所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An）；

n 表示结点中包含的关键字的个数，取值范围是：⌈m/2⌉-1≤ n ≤m-1。Ki （i 从 1 到 n）为关键字，且 Ki < Ki+1 ；Ai 代表指向子树根结点的指针，且指针 Ai-1 所指的子树中所有结点的关键字都小于 Ki，An 所指子树中所有的结点的关键字都大于 Kn。

对于 m 阶的 B-树来说，在定义中规定所有的非终端结点（终端结点即叶子结点，其关键字个数为 0）中包含关键字的个数的范围是[⌈m/2⌉-1,m-1]，所以在插入新的数据元素时，首先向最底层的某个非终端结点中添加，如果该结点中的关键字个数没有超过 m-1，则直接插入成功，否则还需要继续对该结点进行处理。