查找

根据给定的值，在查找表中确定一个关键字等于给定值的数据元素。

  • 关键字：唯一标识一个记录的关键字
  • 次关键字：用以识别若干记录的关键字称之为次关键字。

查找表可以分为两类——静态查找表和动态查找表（查不到要增加，或者查到了就删除）

如何评价查找算法？

平均查找长度：也称为平均比较次数。

线性表的查找

顺序查找

也就是遍历查找

每次循环中都要判断是不是越界了，就影响效率，优化是把关键字放在表头，到头了就得到关键字，省去了每次查找的判断越界。

二分查找

  • ALS（平均查找长度）=log2(n)
  • 缺点:只适用于有序表，且为顺序存储结构。

分块查找

建立索引，索引指向目标附近。

适用情况：快速查找且动态变化的表。

  • 优点：适用于链表。

树表之二叉排序树。

二叉排序树

二叉排序树满足以下条件：其左树的子节点值均小于该节点，右树的子节点值均大于该节点。

  • 性质：中序遍历二叉排序树，得到一个递增有序的序列。
  • 最多比较次数为树的深度。
  • ALS的长度与树形态有关，从log2(n)到o(n)不等。

插入操作

查找直到某个叶子节点的左子树或者右子树为空为止，然后将该节点插入为该节点的子树。

删除操作

  • 若节点为叶子节点，直接删除。
  • 若只有一个子树，将子树替换它。
  • 若有两个子树，使用左子树中最大的值(或者右子树中最小的值)替换它，然后对那个子节点执行删除操作。

失衡二叉树的调整

一个平衡二叉树，在增加一个节点之后，可能发生失衡，这时候就需要调整节点关系，使二叉树保持平衡。

具体操作不好文字描述，略。