静态搜索结构动态搜索结构散列可扩充散列

静态搜索结构动态搜索结构散列可扩充散列内容摘要：

, 将 lc的右子树接成 p的左子树 右重加右 ——左转 结点 p右重 ，还要 加 一个右结点 不平衡 38 13 39 40 45 p rc 4 45 40 38 4 39 p rc 13 左转： 将 p作 rc的左子结点 , 将 rc的左子树接成 p的右子树 左重加左的右 ——双旋 左转再右转 结点 p左重 lc的右子树加一个结点 不平衡 38 13 10 40 20 p lc 26 np 先以 lc np为轴左转 38 13 10 40 20 p lc 26 np 再以 p, np为轴右转 38 13 10 40 20 p lc 26 np 右重加右的左 ——双旋 右转再左转 结点 p右 重 rc的 左 子树加一个结点 不平衡 38 13 55 46 p rc 41 np 先以 rc np为轴 右 转 38 41 67 46 13 p rc 55 np 再以 p, np为轴左转 55 38 13 67 46 np p 41 np 67 AVL树的生成 20 30 80 40 10 60 50 70 49 10 65 60 27 13 1340 20 498030左转 49 65 27 1320 49803049 65 27 1320 498030左重加左的右 左转再右转 20 30 80 40 10 60 50 70 10 60 13 40 49 65 27 1320 498030左重加左的右 左转再右转 10 60 13 40 49 65 27 1320 498030左转 10 60 13 40 49 65 27 1320 498030右转 20 30 80 40 10 60 50 70 10 60 13 40 49 65 27 1320 49803010 60 13 40 49 65 27 1320 49803013 70 13 50 AVL树的高度 设 AVL树高度为 h, 这棵树至少多少结点。 设至少有 nh个结点 n0=0, n1=1 , n2=2, nh+1=nh+nh1+1, nh+1+1=nh+1+nh1+1, 令 fh= nh+1, 则 f0=1, f1=2 , fh+1=fh+fh1 nh = fh1 nh=(51/2)*((1+ 51/2)/2)h+3 1 n个结点的 AVL树的高度 h至多是多少。 n=(51/2)*((1+ 51/2)/2)h+3 1 (n+1)/(51/2)=((1+ 51/2)/2)h+3 log2 (n+1)log251/2= (h+3 )(log2 ((1+ 51/2)/2)) log2 ((1+ 51/2)/2)≈ h+3= (log2 (n+1)log251/2)/ h(3/2) log2 (n+1)1 练习 一 . 画出以下输入所对应 AVL树： 1） R,O,T,A,R,Y,C,L,U,B 2） 60， 25， 7， 99， 15， 3， 10 38， 59， 62， 34 二 . 分别给出这两棵树的前序，中序， 后序遍历输出 三、高度为 5的 AVL树至少几个节点。 15个节点的 AVL树至多多高。 二叉搜索树的查找分析 平均等概率查找时间 (1+2+2+3+3+3)/6=14/6 45 12 57 8 20 60 45 12 8 20 3 11 (1+2+3+4+5+6)/6=7/2 随机二叉搜索树等概率平均查找时间 P(n)≤2(1+1/n)lnn O(log2n) 最坏 O(n/2) 平衡二叉搜索 AVL树的查找分析 求含有 n个关键字的 AVL树的最大深度。 设深度 h的 AVL树的最小结点数为 Nh N0=0, N1=1, N2=2 Nh= Nh1+ Nh2+1 Nh+1= Nh1+1+ Nh2+1 令 F(h)= Nh+1， 则 F(h)=F(h1)+F(h2) Nh Nh1 Nh2 深度 h的 AVL树的最小结点数 Nh F(h)= Nh+1， F(h)=F(h1)+F(h2) F(h)是斐波那契数列 F(1)=1 F(2)=2 F(3)=3 F(4)=5 F(5)=8 N1=0, N2=1, N3=2, N4=4, N5=7, N6=12, 平衡二叉搜索 AVL树的查找分析 设 n个结点的 AVL树的最大深度为 h， 则 Nh=n F(h)=n+1 可以得到 h. h就是最大查找次数 等概率平均查找成功时间复杂性 O(log2n) B树 平衡的多路搜索树 B树的定义 空树 或 m叉树 1) 每个结点至多有 m棵子树， 2) 如根结点不是叶，至少有两棵子树， 3) 除根之外，所有非终端结点至少有 ┌m/2 ┐棵子树 ,本节中记为 [m/2], m=3时 称为 23树 4) 所有的非终端结点含有信息 (n,A0,K1,A1,K2,,Kn,An) [m/2]1个关键字 5) 所有叶结点都在同一层次 ，叫做失败结点。 所有的非终端结点含有信息 n : 有 n+1棵子树， K1≤K2≤≤Kn 关键字有序序列 , 指针 Ai1指向子树中结点的关键字小于 Ki, n A0 K1 A1 K2 Kn An 1 35 1 18 2 43 78 1 11 1 27 1 39 1 99 3 47 53 F F F F F F F F F F F 1 35 1 18 2 43 78 1 11 1 27 1 39 1 99 3 47 53 F F F F F F F F F F F B树的搜索过程 检索结点 53 每增加一个关键字增加一个结点 最底层空结点有 n+1个 B树的查找分析 n个关键字， m阶 B树。