數(shù)據(jù)結(jié)構(gòu)之樹

數(shù)據(jù)結(jié)構(gòu)之樹二叉檢索樹二叉檢索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；它的左、右子樹也分別為二叉檢索樹。二叉檢索樹的基本操作插入在二叉檢索樹中插入新結(jié)點，要保證插入新結(jié)點后仍能滿足二叉檢索樹的性質(zhì)。a、若二叉檢索樹root為空，則使新結(jié)點為根；

b、若二叉檢索樹root不為空，就要先和根結(jié)點的關(guān)鍵字作比較，如果比根結(jié)點的值小，就插入到根結(jié)點的左子樹中，如果比根結(jié)點的值大就插入到根結(jié)點的右子樹中，如此遞歸下去，找到插入的位置。

c、若新結(jié)點的關(guān)鍵字小于插入點的關(guān)鍵字，則將新結(jié)點插入到插入點的左子樹中，大于則插入到插入點的右子樹中。二叉檢索樹的基本操作查找

查找的功能和插入差不多一樣，按照插入那樣的方式遞歸下去，如果找到了，就返回這個節(jié)點的地址，如果沒有找到，就返回NULL。template<classT>TreeNode<T>*BST<T>::findpri(TreeNode<T>*node,Tx){if(node==NULL)//如果結(jié)點為空說明沒找到,返回NULL{returnNULL;}if(node->data>x)//如果x小于結(jié)點的值,就繼續(xù)在結(jié)點的左子樹中查找x{returnfindpri(node->pLChid,x);}elseif(node->data<x){returnfindpri(node->pRChild,x);}elsereturnnode;//如果相等,就找到了此結(jié)點}二叉檢索樹的基本操作刪除二叉檢索樹的刪除，分三種情況進(jìn)行處理：1.p為葉子結(jié)點，直接刪除該結(jié)點，再修改其父結(jié)點的指針（注意分是根結(jié)點和不是根結(jié)點），如圖a。

2.p為單支結(jié)點（即只有左子樹或右子樹）。讓p的子樹與p的父結(jié)點相連，刪除p即可；（注意分是根節(jié)點和不是根節(jié)點）；如圖b二叉檢索樹的基本操作3.P是左右都有孩子的結(jié)點，有一個著名的算法HubbardDeletion。刪除策略是用其右子樹最小的數(shù)據(jù)代替該結(jié)點的數(shù)據(jù)并遞歸的刪除掉右子樹中最小數(shù)據(jù)的結(jié)點。因為右子樹中數(shù)據(jù)最小的結(jié)點肯定沒有左孩子，所以刪除的時候容易一些。如右圖所示，刪除結(jié)點2。堆樹堆樹的定義如下：（1）堆樹是一顆完全二叉樹；（2）堆樹中某個結(jié)點的值總是不大于或不小于其孩子結(jié)點的值；（3）堆樹中每個結(jié)點的子樹都是堆樹。當(dāng)父結(jié)點的鍵值總是大于或等于任何一個子結(jié)點的鍵值時為最大堆。當(dāng)父結(jié)點的鍵值總是小于或等于任何一個子結(jié)點的鍵值時為最小堆。如右圖所示，上邊為最大堆，下邊為最小堆。構(gòu)造最大堆構(gòu)造最大堆在構(gòu)造堆的基本思想就是：首先將每個葉子結(jié)點視為一個堆，再將每個葉子結(jié)點與其父結(jié)點一起構(gòu)造成一個包含更多結(jié)點的對。所以，在構(gòu)造堆的時候，首先需要找到最后一個結(jié)點的父結(jié)點，從這個結(jié)點開始構(gòu)造最大堆；直到該結(jié)點前面所有分支結(jié)點都處理完畢，這樣最大堆就構(gòu)造完畢了。堆樹的基本操作插入（以最小堆為例）1.將新的元素插入到樹中，先直接插入使之成為葉子結(jié)點，同時保證該樹依然是完全二叉樹。若該元素大于其父結(jié)點，兩個元素互換。（上移操作）3.循環(huán)第2步，直至該元素沒有父結(jié)點或小于其父結(jié)點。堆樹的基本操作

刪除（從最小堆1017203038302434）刪除元素則是按照添加元素相反的方向來做，我們需要刪除的元素是堆頂，在這里是最小的那一個元素10，接著我們將最后一位元素放到堆頂?shù)奈恢茫ㄖ暗脑匾呀?jīng)刪除了，所以這里空了一個位置），得到下圖：34

172030383024現(xiàn)在我們將比較堆頂?shù)男略嘏c他的子節(jié)點，如果堆頂新元素比他的子節(jié)點都要大，則將新的堆頂元素與子節(jié)點中較小的元素交換。在這里堆頂元素為34，他的子節(jié)點分別在位置（1*2=2）和（1*2+1=3），即為17和20，34要大于17和20，所以我們將34與17（子節(jié)點中較小的一個）交換，得到下圖：17

34

2030383024

接著我們得到34當(dāng)前所在位置為2（從1開始數(shù)），那么他的子節(jié)點位置分別為（2*2=4）和（2*2+1=5），即為30和38，由于34還是大于他的所有子節(jié)點，交換34與20（子節(jié)點中較小的），得到下圖：173020

34

383024

當(dāng)前34所在位置為4，子節(jié)點位置（4*2=8）和（4*2+1=9），由于當(dāng)前堆的最大長度為7，小于8和9，沒有元素與之對應(yīng)，所以到這里元素刪除完畢。1017302024303834341730202430381734302024303817303420243038字典樹又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。Trie樹的基本性質(zhì)可以歸納為：（1）根結(jié)點不包含字符，除根結(jié)點以外每個結(jié)點只包含一個字符。（2）從根結(jié)點到某一個結(jié)點，路徑上經(jīng)過的字符連接起來，為該結(jié)點對應(yīng)的字符串。（3）每個結(jié)點的所有子結(jié)點包含的字符串不相同。(4)插入和查找的時間復(fù)雜度為O(n),n為字符串長度。

字典樹的基本操作插入對于一個單詞，從根開始，沿著單詞的各個字母所對應(yīng)的樹中的節(jié)點分支向下走，直到單詞遍歷完，將最后的節(jié)點標(biāo)記為紅色，表示該單詞已插入Trie樹。假設(shè)以英文單詞構(gòu)建的字典樹為例，這棵Trie樹中每個結(jié)點包括26個孩子結(jié)點，因為總共有26個英文字母(假設(shè)單詞都是小寫字母組成)。字典樹的基本操作查找(1)每次從根結(jié)點開始一次搜索；(2)取得要查找關(guān)鍵詞的第一個字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索；(3)在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個字母,并進(jìn)一步選擇對應(yīng)的子樹進(jìn)行檢索。(4)迭代過程……

(5)在某個結(jié)點處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點上的信息，即完成查找。

字典樹的應(yīng)用1.字典樹在串的快速檢索中的應(yīng)用。給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。在這道題中先把熟詞建一棵字典樹，然后讀入文章進(jìn)行比較，這種方法效率是比較高的。2.字典樹在“串”排序方面的應(yīng)用給定N個互不相同的僅由一個單詞構(gòu)成的英文名，讓你將他們按字典序從小到大輸出用字典樹進(jìn)行排序，采用數(shù)組的方式創(chuàng)建字典樹，這棵樹的每個結(jié)點的所有兒子很顯然地按照其字母大小排序。對這棵樹進(jìn)行先序遍歷即可3.字典樹在最長公共前綴問題的應(yīng)用對所有串建立字典樹，對于兩個串的最長公共前綴的長度即他們所在的結(jié)點的公共祖先個數(shù)，于是，問題就轉(zhuǎn)化為最近公共祖先問題。R樹一棵R樹滿足如下的性質(zhì)：1.除非它是根結(jié)點之外，所有葉子結(jié)點包含有m至M個記錄索引（條目）。作為根結(jié)點的葉子結(jié)點所具有的記錄個數(shù)可以少于m。通常，m=M/2。2.對于所有在葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形（注意：此處所說的“矩形”是可以擴(kuò)展到高維空間的）。3.每一個飛葉子結(jié)點擁有m至M個孩子結(jié)點，除非它是根結(jié)點。4.對于在非葉子結(jié)點上的每一個條目，i是最小的可以在空間上完全覆蓋這些條目所代表的店的矩形（同性質(zhì)2）。5.所有葉子結(jié)點都位于同一層，因此R樹為平衡樹R樹的作用R樹在數(shù)據(jù)庫等領(lǐng)域做出的功績是非常顯著的。它很好的解決了在高維空間搜索等問題。舉個R樹在現(xiàn)實領(lǐng)域中能夠解決的例子吧：查找20英里以內(nèi)所有的餐廳。如果沒有R樹你會怎么解決？一般情況下我們會把餐廳的坐標(biāo)(x,y)分為兩個字段存放在數(shù)據(jù)庫中，一個字段記錄經(jīng)度，另一個字段記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然后計算是否滿足要求。如果一個地區(qū)有100家餐廳的話，我們就要進(jìn)行100次位置計算操作了，如果應(yīng)用到谷歌地圖這種超大數(shù)據(jù)庫中，我想這種方法肯定不可行吧。R樹就很好的解決了這種高維空間搜索問題。它把B樹的思想很好的擴(kuò)展到了多維空間，采用了B樹分割空間的思想，并在添加、刪除操作時采用合并、分解結(jié)點的方法，保證樹的平衡性。因此，R樹就是一棵用來存儲高維數(shù)據(jù)的平衡樹。R樹的數(shù)據(jù)結(jié)構(gòu)R樹是B樹在高維空間的擴(kuò)展，是一棵平衡樹。每個R樹的葉子結(jié)點包含了多個指向不同數(shù)據(jù)的指針，這些數(shù)據(jù)可以是存放在硬盤中的，也可以是存在內(nèi)存中。根據(jù)R樹的這種數(shù)據(jù)結(jié)構(gòu)，當(dāng)我們需要進(jìn)行一個高維空間查詢時，我們只需要遍歷少數(shù)幾個葉子結(jié)點所包含的指針，查看這些指針指向的數(shù)據(jù)是否滿