第七章 搜索结构 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

本章主要内容 搜索的概念 静态搜索结构 顺序搜索 有序顺序表 折半搜索 斐波那契搜索 二叉搜索树

搜索的概念 在数据集合中寻找满足某种条件的数据元素 可唯一标识一个元素的属性称为关键字(key) 衡量搜索算法时间效率的标准 搜索可能成功 也可能不成功 可唯一标识一个元素的属性称为关键字(key) 基于关键字的搜索结果是唯一的 基于其他属性的搜索结果可能不唯一 衡量搜索算法时间效率的标准 平均比较次数，或平均搜索长度(ASL)

顺序搜索 从表头(或尾)开始，依次用各对象的关键字与给定值x比较 若值相等，搜索成功，返回下标 若整个表都未找到，搜索失败 … 搜索成功的平均搜索长度： pi: 搜索第 i 个元素概率 ci: 搜索到第 i 个元素所需比较次数 pi=1/n ci=i+1 n个元素 搜索不成功的平均搜索长度 … ASLunsucc = n+1

有序顺序表 顺序搜索 从表头(或尾)开始，依次用各对象的关键字与给定值x比较 … 若值相等，搜索成功，返回下标 若x比关键字大时，搜索失败 搜索成功的平均搜索长度： n个元素，n+1个空档 搜索不成功的平均搜索长度 …

有序顺序表 折半搜索 x先和mid元素比较 搜索成功 若相等，搜索成功，返回下标 若x更小，继续在前半部分搜索 若x更大，继续在后半部分搜索 搜索40 10 20 30 40 50 60 1 2 3 4 5 折半搜索 low=0, high=n-1,mid=(low+high)/2 x先和mid元素比较 若相等，搜索成功，返回下标 若x更小，继续在前半部分搜索 high=mid-1, mid=(low+high)/2 若x更大，继续在后半部分搜索 low=mid+1, mid=(low+high)/2 low mid high 40>30 10 20 30 40 50 60 1 2 3 4 5 low mid high 40<50 10 20 30 40 50 60 1 2 3 4 5 low mid high 40=40 搜索成功

有序顺序表 折半搜索 x先和mid元素比较 low>high，搜索失败 若相等，搜索成功，返回下标 若x更小，继续在前半部分搜索 搜索25 10 20 30 40 50 60 1 2 3 4 5 折半搜索 low=0, high=n-1,mid=(low+high)/2 x先和mid元素比较 若相等，搜索成功，返回下标 若x更小，继续在前半部分搜索 high=mid-1, mid=(low+high)/2 若x更大，继续在后半部分搜索 low=mid+1, mid=(low+high)/2 low mid high 25<30 10 20 30 40 50 60 1 2 3 4 5 low mid high 25>10 10 20 30 40 50 60 1 2 3 4 5 10 20 30 40 50 60 1 2 3 4 5 mid high low low mid high 25>20 low>high，搜索失败

有序顺序表 折半搜索 折半搜索构造的判定树 设满二叉树n=2h-1 则有2h=n+1，h=log2(n+1) 平均搜索长度 50 = 30 < > 20 40 60 10 折半搜索 折半搜索构造的判定树 设满二叉树n=2h-1 则有2h=n+1，h=log2(n+1) 平均搜索长度 错位相减法

二叉搜索树 二叉搜索树的概念 或者是空树 或者具有以下性质 每个结点都有一个关键字(key) 左子树上所有结点的key小于根结点的key 左子树和右子树也是二叉搜索树

二叉搜索树 搜索x操作 从根开始搜索x 若当前结点为空，则搜索失败，否则 x小于当前结点key，在左子树搜索 53 65 87 81 94 78 09 45 23 17 搜索23

二叉搜索树 搜索x操作 从根开始搜索x 若当前结点为空，则搜索失败，否则 x小于当前结点key，在左子树搜索 53 65 87 81 94 78 09 45 23 17 搜索94

二叉搜索树 插入x操作 从根开始搜索x，若存在，放弃 否则搜索到叶子结点时 x小于叶子结点key，作为叶子结点左孩子 53 65 87 81 94 78 09 45 23 17 插入88 88

二叉搜索树 删除x操作 从根开始搜索x，若不存在，放弃；否则： x只有左子树，左孩子填补 x只有右子树，右孩子填补 x有左右子树，右子树上中序第一结点v (左走直到头)填补，用v的右孩子填补v 53 17 78 删除45 09 45 65 87 23 81 94

二叉搜索树 删除x操作 从根开始搜索x，若不存在，放弃；否则： x只有左子树，左孩子填补 x只有右子树，右孩子填补 x有左右子树，右子树上中序第一结点v (左走直到头)填补，用v的右孩子填补v 53 17 78 删除78 09 45 94 88 23

二叉搜索树 删除x操作 从根开始搜索x，若不存在，放弃；否则： x只有左子树，左孩子填补 x只有右子树，右孩子填补 x有左右子树，右子树上中序第一结点v (左走直到头)填补，用v的右孩子填补v 53 17 78 删除78 65 99 09 45 94 23 81 81 88

二叉搜索树 性能分析 满二叉树 中间结点等概率搜索， 中间结点数为n 叶子为搜索失败情况 其他为key 叶子结点等概率搜索，

二叉搜索树 性能分析 一般二叉树 随机情况下，二叉树操作代价平均为O(log2n) p(n)表示在一棵有n个结点的二叉树上 成功搜索一个关键值的平均比较次数 叶子为搜索失败情况 其他为key 根 左子树有i个结点 右子树有n-i-1个结点 随机情况下，二叉树操作代价平均为O(log2n)

二叉搜索树 性能分析 一般二叉树 pi：搜索中间结点 i 概率 叶子为搜索失败情况 hi：j深度 其他为key qj：搜索叶子结点 j 概率 hj：j的深度

二叉搜索树 最优二叉搜索树 假设有n个key，每个key搜索概率不同，除key之外的值(即搜索不成功情况)搜索概率也不同，构造平均搜索长度最小的二叉树 例如，3个key ={10，20，30}，每个key搜索概率为P={0.5, 0.1, 0.05}，除key之外(空隙中)的值搜索概率为Q={0.15, 0.1, 0.05, 0.05} 10 20 30 0.5 0.1 0.05 0.15

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度)，则C(0,n)是最后结果 w(i,j)表示第 i+1 到 j 个key权值及第i到j个空隙权值和 w(i,j) = (qi+…+qj) + (pi+1+…+ pj) 10 20 30 p1 p2 p3 q0 q1 q2 q3 40 50 60 p4 p5 p6 q4 q5 q6 W(2,5)=(q2+q3+q4+q5) + (p3+p4+p5)

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度)，则C(0,n)是最后结果 w(i,j)表示第 i+1 到 j 个key权值及第i到j个空隙权值和 w(i,j) = (qi+…+qj) + (pi+1+…+ pj) i+1, … , j以k为根的最优二叉树代价： = pk + c(i,k-1)+w(i,k-1) + c(k,j)+w(k,j) 左子树的代价 右子树的代价 根的代价 左子树加一层的代价 右子树加一层的代价

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度)，则C(0,n)是最后结果 w(i,j)表示第 i+1 到 j 个key权值及第i到j个空隙权值和 w(i,j) = (qi+…+qj) + (pi+1+…+ pj) i+1, … , j以k为根的最优二叉树代价： = pk + c(i,k-1)+w(i,k-1) + c(k,j)+w(k,j) = w(i,j) + c(i,k-1) + c(k,j) 左子树的代价 树上权值和 右子树的代价

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度)，则C(0,n)是最后结果 w(i,j)表示第 i+1 到 j 个key权值及第i到j个空隙权值和 w(i,j) = (qi+…+qj) + (pi+1+…+ pj) i+1, … , j以k为根的最优二叉树代价： = pk + c(i,k-1)+w(i,k-1) + c(k,j)+w(k,j) = w(i,j) + c(i,k-1) + c(k,j) i+1, … , j的最优二叉树代价： c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j 树上权值和 左右子树代价和最小值

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p1 p2 p3 p4 p5 p6 10 20 30 40 50 60 q0 q1 q2 q3 q4 q5 q6 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p1 10 p2 p3 p4 p5 p6 q0 20 30 40 50 60 q1 q2 q3 q4 q5 q6 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p2 20 p1 p3 p4 p5 p6 10 30 40 50 60 q0 q1 q2 q3 q4 q5 q6 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p3 30 p1 p2 p4 p5 p6 10 20 40 50 60 q0 q1 q2 q3 q4 q5 q6 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p4 40 p1 p2 p3 p5 p6 10 20 30 50 60 q0 q1 q2 q3 q4 q5 q6 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p5 50 p1 p2 p3 p4 p6 10 20 30 40 60 q0 q1 q2 q3 q4 q5 q6 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 给定n个key，第i个key对应的权值(概率)pi，空隙对应的权值qi，造平均搜索长度最小的二叉树 c(i,j)表示第 i+1 到 j 个key构造的最优二叉树的代价(平均搜索长度) c(i,j) = w(i,j) + min{ c(i,k-1) + c(k,j) }, 其中i < k ≤ j p6 60 p1 p2 p3 p4 p5 10 20 30 40 50 q6 q0 q1 q2 q3 q4 q5 c(0,6)=w(0,6)+min{c(0,k)+c(k,6)}, 0 < k ≤ 6

二叉搜索树 最优二叉搜索树 第1步：各key自成二叉树，计算平均搜索长度c，保留最小值 10 20 30 10 20 30 W=0.75 0.5 0.1 0.05 0.15 最优二叉搜索树 第1步：各key自成二叉树，计算平均搜索长度c，保留最小值 10 0.5 0.15 0.1 20 0.1 0.05 30 0.05 W=0.75 W=0.25 W=0.15 c(0,1)=0.75 c(1,2)=0.25 c(2,3)=0.15 c(0,1)=0.75 c(1,2)=0.25 w等于树上所有结点(内部和外部)的权值和， c等于w加上左右子树的代价 c(2,3)=0.15

二叉搜索树 最优二叉搜索树 第2步：相邻2个key成二叉树, 计算平均搜索长度c 保留最小值 10 20 30 20 10 c(1,2) 0.5 0.1 0.05 0.15 最优二叉搜索树 第2步：相邻2个key成二叉树, 计算平均搜索长度c 保留最小值 20 0.1 0.05 10 0.5 0.15 c(1,2) 10 0.5 0.15 0.1 20 0.05 c(0,1) 30 0.05 20 0.1 c(2,3) 20 0.1 0.05 30 c(1,2) c(0,2)=w+c(1,2) =1.15 c(0,2)=w+c(0,1) =1.65 c(1,3)=w+c(2,3) =0.5 c(1,3)=w+c(0,1) =0.6 c(0,1)=0.75 c(0,2)=1.15 c(1,2)=0.25 c(1,3)=0.5 w等于树上所有结点(内部和外部)的权值和， c等于w加上左右子树的代价 c(2,3)=0.15

二叉搜索树 最优二叉搜索树 第3步：相邻3个key成二叉树, 计算平均搜索长度c 保留最小值 10 20 30 20 10 30 20 10 0.5 0.1 0.05 0.15 最优二叉搜索树 第3步：相邻3个key成二叉树, 计算平均搜索长度c 保留最小值 20 0.1 10 0.5 0.15 30 0.05 20 0.1 0.05 10 0.5 0.15 30 30 0.05 20 0.1 10 0.5 0.15 c(0,3)=w+c(1,3) =1.5 c(0,3)=w+c(0,1)+c(2,3) =1.9 c(0,3)=w+c(0,2) =2.15 c(0,1)=0.75 c(0,2)=1.15 c(0,3)=1.5 c(1,2)=0.25 c(1,3)=0.5 w等于树上所有结点(内部和外部)的权值和， c等于w加上左右子树的代价 c(2,3)=0.15