找工作——数据结构

静态查找表：只做查找操作的查找表

动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

如果查找的数据集是有序线性表，并且是顺序存储的，查找可以使用折半、插值、斐波那契等查找算法，可以，因为有序，在插入和删除操作上，就需要耗费大量的时间。

二叉排序树

　　定义：

• 又称为二叉查找树，它或者是一颗空树或者是具有下列性质的二叉树。
• 若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值；
• 若它的有子树部位空，则右子树上所有结点的值均大于它的根节点的值；
• 它的左右子树也分别为二叉排序树。

　　构建过程

　　删除操作：

　　　　如果是叶节点直接删除；

　　　　如果要删除的只有左子树或右子树，那就将该结点删除后，将它的左子树或右子树整个移动到删除的结点的位置即可；

　　　　如果要删除的是左右子树都有的结点，找到需要删除的结点p的直接前驱（或直接后继），用s来替换结点p，然后再删除此结点s。

　　总结：对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的成熟，因此二叉排序树的查找性能取决于二叉排序树的形状。我们希望，二叉排序树是比较平衡的，即其深度与完全二叉树相同，则查找的时间复杂度为logN，近似于折半查找。

平衡二叉树（AVL）：是一种二叉排序树，其中每一个结点的左子树和右子树的高度差之多等于1.

红黑树：http://blog.csdn.net/eric491179912/article/details/6179908

多路查找树（B树）：

原文：http://www.cnblogs.com/java-cjt/p/5263832.html