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

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

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

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

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

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

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

34

2030383024

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

34

383024

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

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

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

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