靜態(tài)搜索結(jié)構(gòu)動(dòng)態(tài)搜索結(jié)構(gòu)散列可擴(kuò)充散列(編輯修改稿)
2024-11-03 08:23 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 , 將 lc的右子樹(shù)接成 p的左子樹(shù) 右重加右 ——左轉(zhuǎn) 結(jié)點(diǎn) p右重 ，還要 加 一個(gè)右結(jié)點(diǎn) 不平衡 38 13 39 40 45 p rc 4 45 40 38 4 39 p rc 13 左轉(zhuǎn)： 將 p作 rc的左子結(jié)點(diǎn) , 將 rc的左子樹(shù)接成 p的右子樹(shù) 左重加左的右 ——雙旋 左轉(zhuǎn)再右轉(zhuǎn) 結(jié)點(diǎn) p左重 lc的右子樹(shù)加一個(gè)結(jié)點(diǎn) 不平衡 38 13 10 40 20 p lc 26 np 先以 lc np為軸左轉(zhuǎn) 38 13 10 40 20 p lc 26 np 再以 p, np為軸右轉(zhuǎn) 38 13 10 40 20 p lc 26 np 右重加右的左 ——雙旋 右轉(zhuǎn)再左轉(zhuǎn) 結(jié)點(diǎn) p右 重 rc的 左 子樹(shù)加一個(gè)結(jié)點(diǎn) 不平衡 38 13 55 46 p rc 41 np 先以 rc np為軸 右 轉(zhuǎn) 38 41 67 46 13 p rc 55 np 再以 p, np為軸左轉(zhuǎn) 55 38 13 67 46 np p 41 np 67 AVL樹(shù)的生成 20 30 80 40 10 60 50 70 49 10 65 60 27 13 1340 20 498030左轉(zhuǎn) 49 65 27 1320 49803049 65 27 1320 498030左重加左的右 左轉(zhuǎn)再右轉(zhuǎn) 20 30 80 40 10 60 50 70 10 60 13 40 49 65 27 1320 498030左重加左的右 左轉(zhuǎn)再右轉(zhuǎn) 10 60 13 40 49 65 27 1320 498030左轉(zhuǎn) 10 60 13 40 49 65 27 1320 498030右轉(zhuǎn) 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樹(shù)的高度 設(shè) AVL樹(shù)高度為 h, 這棵樹(shù)至少多少結(jié)點(diǎn)？ 設(shè)至少有 nh個(gè)結(jié)點(diǎn) 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個(gè)結(jié)點(diǎn)的 AVL樹(shù)的高度 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 練習(xí) 一 . 畫出以下輸入所對(duì)應(yīng) AVL樹(shù)： 1） R,O,T,A,R,Y,C,L,U,B 2） 60， 25， 7， 99， 15， 3， 10 38， 59， 62， 34 二 . 分別給出這兩棵樹(shù)的前序，中序， 后序遍歷輸出 三、高度為 5的 AVL樹(shù)至少幾個(gè)節(jié)點(diǎn)。 15個(gè)節(jié)點(diǎn)的 AVL樹(shù)至多多高？ 二叉搜索樹(shù)的查找分析 平均等概率查找時(shí)間 (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 隨機(jī)二叉搜索樹(shù)等概率平均查找時(shí)間 P(n)≤2(1+1/n)lnn O(log2n) 最壞 O(n/2) 平衡二叉搜索 AVL樹(shù)的查找分析 求含有 n個(gè)關(guān)鍵字的 AVL樹(shù)的最大深度？ 設(shè)深度 h的 AVL樹(shù)的最小結(jié)點(diǎn)數(shù)為 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樹(shù)的最小結(jié)點(diǎn)數(shù) Nh F(h)= Nh+1， F(h)=F(h1)+F(h2) F(h)是斐波那契數(shù)列 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樹(shù)的查找分析 設(shè) n個(gè)結(jié)點(diǎn)的 AVL樹(shù)的最大深度為 h， 則 Nh=n F(h)=n+1 可以得到 h. h就是最大查找次數(shù) 等概率平均查找成功時(shí)間復(fù)雜性 O(log2n) B樹(shù) 平衡的多路搜索樹(shù) B樹(shù)的定義 空樹(shù) 或 m叉樹(shù) 1) 每個(gè)結(jié)點(diǎn)至多有 m棵子樹(shù)， 2) 如根結(jié)點(diǎn)不是葉，至少有兩棵子樹(shù)， 3) 除根之外，所有非終端結(jié)點(diǎn)至少有 ┌m/2 ┐棵子樹(shù) ,本節(jié)中記為 [m/2], m=3時(shí) 稱為 23樹(shù) 4) 所有的非終端結(jié)點(diǎn)含有信息 (n,A0,K1,A1,K2,,Kn,An) [m/2]1個(gè)關(guān)鍵字 5) 所有葉結(jié)點(diǎn)都在同一層次 ，叫做失敗結(jié)點(diǎn)。 所有的非終端結(jié)點(diǎn)含有信息 n : 有 n+1棵子樹(shù)， K1≤K2≤≤Kn 關(guān)鍵字有序序列 , 指針 Ai1指向子樹(shù)中結(jié)點(diǎn)的關(guān)鍵字小于 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樹(shù)的搜索過(guò)程 檢索結(jié)點(diǎn) 53 每增加一個(gè)關(guān)鍵字增加一個(gè)結(jié)點(diǎn) 最底層空結(jié)點(diǎn)有 n+1個(gè) B樹(shù)的查找分析 n個(gè)關(guān)鍵字， m階 B樹(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1