数据结构——查找

数据结构——查找

一.静态查找表

1.顺序查找

ASL=pici=1/nn-i+1=(n+1)/2

2.折半查找

ASL=pici=1/nj*2（j-1）次方=log2（n+1）-1

3.分块查找（索引顺序查找）

二.动态查找表

1.二叉排序树

（1）若它的左子树非空，则左子树上所有结点的值小于根结点的值。

（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。

（3）左右子树本身就是两棵二叉排序树。

2.平衡二叉树

3.B-数

（1）树中每个结点至多有m棵子树。

（2）若根结点不是叶子结点，则至少有两棵树。

（3）除根之外的所有非终端结点至少有m/2（取最大）棵子树。

（4）所有的非终端结点中包含下列数据信息（n,A0,K1,A1,K2,…,Kn,An）其中Ki为关键字，且Ki

（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看做是外部结点或者查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）

三.哈希查找表

Hash（key）=key mod m

处理冲突方法：线性探测再散列、二次探测再散列、随机探测再散列