JS-7种查找算法之树表查找、索引查找（分块查找）、哈希查找原理

原文链接 https://www.cnblogs.com/yw09041432/p/5908444.html

5. 树表查找（在数据结构树中有实现）

　　5.1 最简单的树表查找算法——二叉树查找算法。(在数据结构二叉树中有实现)

　　基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

　　　　二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

　　　　1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　　　2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

　　　　3）任意节点的左、右子树也分别为二叉查找树。

　　　　二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

 

6. 索引查找（分块查找）

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

　　算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

　　算法流程：

　　step1 先选取各块中的最大关键字构成一个索引表；

　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

 

7.哈希查找

　　哈希查找和哈希算法看这里

　　哈希查找  https://www.cnblogs.com/yw09041432/p/5908444.html

　　哈希算法  https://www.cnblogs.com/xiohao/p/4389672.html   http://www.sohu.com/a/232586831_100078137