查找表（Search Table）

• 查找表是由同一类型的数据元素（或记录）构成的集合

• 对查找表进行的操作有：
  • 查询某个元素是否在表中
  • 检索某个元素的各种属性
  • 在查找表中插入一个数据元素
  • 在查找表中删除某个数据元素

• 若对查找表只做前两种统称为查找的操作，则称为静态查找表（Static Search Table）,若还进行插入或删除操作，称其为动态查找表（Dynamic Search Table）
• 关键字（Key）：是数据元素中某个数据项的值，可以标识一个数据元素
• 主关键字（Primary Key）：此关键字可以唯一地标识一个记录
• 次关键字（Secondary Key）：用以标识若干记录的关键字
• 平均查找长度（Average Search Length - ALS）：需和给定值进行比较的关键字的个数的期望值

静态查找表

顺序查找（Sequential Search）

• 逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值相等，则查找成功
• 平均查找长度较大，当n很大时，查找效率低
• 算法简单且适用面广

折半查找（Binary Search）

• 有序表，且限于顺序存储结构，对线性链表无法有效进行折半查找
• 先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止
• 类似还有斐波那契查找和插值查找

*静态树表的查找

索引顺序查找

• 又称分块查找
• 需建立一个索引表
• 将表分为多个子表，每个子表建立一个索引项，其中包含：
  • 关键字项：其值为该子表内最大关键字
  • 指针项：指示该子表的第一个记录在表中的位置
• 索引表按关键字有序，表有序或分块有序
• 查找过程：先根据索引表确定待查记录所在的块（子表），然后在块中顺序查找（块内有序可用折半查找）

动态查找表

• 特点：表结构本身是在查找过程中动态生成的，即对于给顶值key，若表中存在，则返回查找结果，若不存在，则插入关键字等于key的记录

二叉排序树（Binary Sort Tree）

• 二叉排序树若不为空，则具有下列性质：
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左右子树也分别为二叉排序树。
• 又称二叉查找树
• 查找：
  • 先查找其根节点，如果根节点的数据与key值相等，则返回该根节点，并且返回TRUE；
  • 否则， 如果key值大于根节点，则查询其右子树；
  • 如果小于根节点，则查询其左子树。
• 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点
• 删除二叉排序树的*p结点：
  • 若*p结点为叶子结点，即P_L和P_R均为空树。由于删除叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可
  • 若*p结点只有左子树P_L或只有右子树P_R，此时只要令P_L或P_R直接成为其双亲结点的左子树即可。
  • 若*p结点的左子树和右子树均不空。为保持其他元素的相对不变，可以有两种做法：一是先直接令P_L为*f的左子树，再令P_R为PL子树中最右孩子的右子树。P_L子树中最右孩子即为P_L子树中最大的结点。二是令*p的直接前驱(或直接后继)代替*p，然后从二叉排序树中删除它的直接前驱(或直接后继)。*p的直接前驱为P_L子树中最右孩子，大小仅次于*p；*p的直接后继为P_R子树中最左孩子，大小仅大于*p。

平衡二叉树（Balanced Binary Tree)

• 又称AVL树
• 若平衡二叉树不为空，则它的左子树和右子树都是平衡二叉树，切左子树和右子树的深度之差的绝对值不超过1。
• 平衡因子BF（Balance Factor）定义为该结点的左子树的深度减去它的右子树的深度。
• 只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的
• 二叉排序树插入结点后失去平衡后进行调整：
  • 单向右旋平衡处理
  • 单向左旋平衡处理
  • 双向旋转（先左后右）平衡处理
  • 双向旋转（先右后左）平衡处理

B-树

• 一种平衡的多路查找树
• 。。。。。。

B⁺树

• 应文件系统所需而出的一种B-树的变形树
• 。。。。。。

*键树

• 又称数字查找树（Digital Search Trees）