排序查找是我自己觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!
查找
一、 知识点 /静态查找->数组
1、 什么是查找
\动态查找->链树
●顺序查找，时间复杂度 O(n)
●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度)
●索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素。
算法：根据index来确定X所在的块（i） 时间复杂度：m/2
在第Ｉ块里顺序查找X 时间复杂度：n/2
总的时间复杂度：(m+n)/2
●二叉排序树 1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。
2）特点：中序遍历有序->（删除节点用到此性质）
3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。
4）结点的插入->二叉排序树的构造方法
5）结点删除（难点） 1、右子树放在左子树的最右边
2、左子树放在右子树的最左边
●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。
●B树：n阶B树满足以下条件 1）每个结点（除根外）包含有N～2N个关链字。 2）所有叶子节点都在同一层。
3）B树的所有子树也是一棵B树。
特点：降低层次数，减少比较次数。
[1] [2] [3] 下一页
上一篇文章： 考试辅导：程序员数据结构笔记（二）下一篇文章： 考试辅导：程序员数据结构笔记（三） 【
发表评论】【
加入收藏】【
告诉好友】【
打印此文】【
关闭窗口】
