【正文】 A， B（ 1 = A,B = N , A不等于 B），代表 A， B為朋友關系。 【輸入文件】 ? 輸入文件的第一行有 2個正整數(shù) N 和 M 。根據(jù)有名的諺語：“我朋友的朋友也是我的朋友”，所以如果 A和 B是朋友， B和 C是朋友，那么 A和 C也是朋友。 應 用 1： friend ? 有一個鎮(zhèn)有 N個居民。 ? } 并查集的時間復雜度 ? 可以證明，經過啟發(fā)式合并和路徑壓縮之后的并查集，執(zhí)行 m次查找的復雜度為O(mα(m)) ? 其中 α(m)是 Ackermann函數(shù)的某個反函數(shù)，你可以近似的認為它是小于 5的。 ? father[t]=f。 ? end。 ? father[t]:=f。 ? return。 ? y=find(y)。 ? end。 ? y:=find(y)。 ? } 啟發(fā)式合并 如何合并？ ? procedure unionxy(x,y:longint)。 ? while(father[f]!=0) f=father[f]。 ? int find(int t) ? { ? int f。 ? find:=f。 ? begin ? f:=t。 ? 如果 t為根，則 father[t]=0 如何尋找根節(jié)點？ ? function find(t:longint):longint。接下來 m行，表示 m次操作。則有： ??? ???，其他情況是基元，0],1[1)(1)(ijw or dandjfif時間復雜度分析 ? 每次求 f(i)需要向前找 f(j)， ijL,每移動一次 j需要判定 word(j+1,i)是否是單詞 ? 1=i=len(T),1=ijL ? 查找單詞時間復雜度為 O(L) ? 因此總時間復雜度為 O(len(T)*L2)。 ? 這樣我們只需要 O(L)的時間即可查找到某個單詞， L為單詞的長度。如下圖為樣例的單詞樹。 ? 每個節(jié)點的所有兒子包含的字母都不相同。 ? 例如，需要保存“ puter”和“ mand”，由于它們的前三個字母是相同的，所以希望它們共享前三個字母，而只有剩下部分才進行分開儲存。 ? （ N=80000，等待的寵物 /領養(yǎng)者數(shù) M=10000） 字典樹（ trie） ? 當關鍵字是串的時候，往往用 trie。X=1表示領養(yǎng)人， Y為特征值。并且紀錄兩個特點值的差值。領養(yǎng)人所希望的特點值也不相同。 ? 可見在 Splay樹的基本操作中，處處要用到 Splay旋轉操作！ 應用： Pet ? 寵物收養(yǎng)場提供兩種服務：收養(yǎng)被離棄的寵物與讓新的主人領養(yǎng)寵物。然后將新元素旋轉到根。 Splay操作舉例 Splay(1,S) Spaly樹基本操作 ? 查找：與二叉排序樹查找類似，只是查找結束后要將找到的元素通過 Splay操作旋轉到根。 Splay操作 情況 2 ? ZigZig或 ZagZag操作： ? 節(jié)點 x的父節(jié)點 y不是根節(jié)點，且 x與 y同時是各自父節(jié)點的左孩子或者同時是各自父節(jié)點的右孩子。 Splay操作 ? Splay操作 是在保持 Splay樹有序性的前提下，通過一系列旋轉操作將樹中的元素 x調整至樹的根部的操作 (Zig:右旋 ,Zag:左旋 )。 即 Splay樹中的每一個節(jié)點 x都滿足：該節(jié)點左子樹中的每一個元素都小于 x，而其右子樹中的每一個元素都大于 x。 ? 對 Splay樹的操作的均攤復雜度是 O(log2n)。 ? 某些二 叉查找樹的變形，基本操作在最壞情況下性能依然很好，如紅黑樹、 AVL樹 等。 ? n=100000 樣例 7 表示有 7個數(shù) 3 2 6 5 7 4 1 二叉查找樹時間復雜度分析 ? 二叉查找樹 (Binary Search Tree) 可以被用來表示有序集合、建立索引或優(yōu)先隊列等。s:=s^.rchild] p^.data:=s^.data。s:=p^.lchild?；蛘?f^.lchild:=P^.rchild。 else f^.rchild:=s end。 if bst=nil then bst:=s。s^.lchild:=nil。 {采用鏈式存儲結構 } begin new(s)。 BST插入的遞歸算法 PROC ins_bstree(var bst:bitree。 ? 子樹中的插入過程與上述的樹中插入過程相同。 (ii)keyT→key，則將 key插入根的左子樹中。K:keytype):bitree if (t=nil) or (t^.key=K) then return(t) else if t^.keyK then return(bstsrch(t^.lchild,k)) else return(bstsrch(t^.rchild,k)) endF BST的插入 ? 在二叉排序樹中插入新結點，要保證插入后仍滿足 BST性質。 （ 3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。 （ 2） 二叉排序樹中，各結點關鍵字是惟一的。 1)若 F為空，即 m=0,則 B為空樹 2)若 F非空，即 m0,則 B的根 root即為森林中第一棵樹的根 root(T1),B的左子樹為從 T1中子樹森林 F1={T11, T12, …,T1i}轉換而成的二叉樹；其右子樹 Rb 是從森林F={T2, …,Tm}中轉換出來的二叉樹 二叉排序樹 (Binary Sort Tree) ? 二叉排序樹又稱為二叉查找 (搜索 )樹 (BST) ? 它或者是一顆空樹，或者是具有如下性質的二叉樹： – 1)若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值 – 2) 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值 – 3)它左右子樹分別為二叉排序樹。 preorder(bt^.rchild)。 二叉樹的遍歷 ? 遍歷 ( 先序遍歷 , 中序遍歷 , 后序遍歷 ) Proc preorder(bt:bitree)。 lchild,rchild:bitree。 根的層次 =