程序员数据结构笔记（三）

排序查找是我自己觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!

查找

一、 知识点　　　　/静态查找->数组　　　　
　　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树。
　　　特点：降低层次数，减少比较次数。