静态查找表&动态查找表

静态查找表：只查找，不改变集合内的数据元素。

一、顺序查找（ Linear search，又称线性查找 ）用逐一比较的办法顺序查找关键字。

1、顺序查找时间复杂度：O(n)

2、顺序查找平均查找长度 ASL=(n+1)/2

顺序查找

二、折半查找前提是顺序存储，记录有序。

思想：与记录中间值比较，如果比中间值小去左边查，否则去右边查找，直到找到为止，区域内没记录时查找失败。

1、折半查找时间复杂度：O()

2、折半查找平均查找长度  ASL=

折半查找

动态查找表：既查找，又改变（增减）集合内的数据元素。

二叉排序树满足下列性质

1）若左子树不为空，则左子树上的所有结点的值（关键字）都小于根节点的值；

2）若右子树不为空，则右子树上的所有结点的值（关键字）都大于根节点的值；

3）左、右子树都分别为二叉排序树。

二叉排序树的查找思想

1）首先将给定的K值与二叉排序树的根节点的关键字进行比较：若相等，则查找成功；

2）若给定的K值小于二叉排序树的根节点的关键字：继续在该节点的左子树上进行查找；

3）若给定的K值大于二叉排序树的根节点的关键字：继续在该节点的右子树上进行查找。

二叉排序树总结

1）查找过程与顺序结构有序表中的折半查找相似，查找效率高；

2）中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；

3）如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。