静态查找表：只查找，不改变集合内的数据元素。
一、顺序查找（ 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）如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。
网友评论