高等數(shù)據(jù)結(jié)構(gòu)與算法分析4

Chapter3

AdvancedTreeStructuresThischapterintroducesseveraltreestructuresdesignedforuseinspecializedapplications.

1.Tries2.BalancedTrees3.SpatialDataStructures1.Tries2.BalancedTrees3.SpatialDataStructuresiscommanlyusedtostorestringsandissuitableforstoringandsearchingcollectionsofstrings.用于存儲字符串，適合于字典的存儲和檢索arevariantsontheBST.Theyareexamplesofself-balancingsearchtreesandhaveguaranteedgoodperformanceregardlessoftheinsertionorderforrecords.BST的變體，是自平衡檢索樹Usedtoorganizepointdatabyxy-coordinates.1、TriesThedatastructurebasedonObjectSpacedecomposition

基于對象空間分解的數(shù)據(jù)結(jié)構(gòu)

TheshapeofaBSTdependsontheorderinwhichitsdatarecordsareinserted.BST的形狀依賴于數(shù)據(jù)記錄插入順序TheresultingBSTmightbebalancedorunbalanced.----thedecompositionofthekeyrangeisdrivenbytheobjectsstoredinthetree.關(guān)鍵碼范圍的分解是由存儲在樹中的對象驅(qū)動的ThedatastructurebasedonKeySpacedecomposition

基于關(guān)鍵碼空間分解的數(shù)據(jù)結(jié)構(gòu)

1、TriesThedatastructurebasedonObjectSpacedecomposition

基于對象空間分解的數(shù)據(jù)結(jié)構(gòu)ThedatastructurebasedonKeySpacedecomposition

基于關(guān)鍵碼空間分解的數(shù)據(jù)結(jié)構(gòu)

Topredefinethesplittingpositionwithinthesplittingpositionwithinthekeyrangeforeachnodeinthetree.Inotherwords,therootcouldbepredefinedtosplitthekeyrangeintotwoequalhalves.,regardlessoftheparticularvaluesororderofinsertionforthedatarecords.對樹結(jié)構(gòu)中每一結(jié)點(diǎn)在關(guān)鍵碼范圍預(yù)定義劃分位置。也就是說，應(yīng)當(dāng)預(yù)定義根結(jié)點(diǎn)，把關(guān)鍵碼范圍劃分成相等的兩半，而不管數(shù)據(jù)記錄的具體值或者插入順序。Decompositionbasedonequalsubdivisionofthekeyrangeiscalledkeyspacedecomposition.基于關(guān)鍵碼范圍相等子劃分的分解稱為關(guān)鍵碼空間分解稱為一個Trie結(jié)構(gòu)LiketheB＋-tree，atriestoresdatarecordsonlyinleafnodes.Internalnodesserveasplaceholderstodirectthesearchprocess.Trie結(jié)構(gòu)只在葉結(jié)點(diǎn)存儲數(shù)據(jù)記錄，內(nèi)部結(jié)點(diǎn)只作占位符占據(jù)位置，并引導(dǎo)檢索過程。Example1.Thebinarytrieforthesetofvalues〔2，7，24，32，37，40，42，120〕Example

2.Huffmancodingtree1、TriesBinaryTriesForbinarynumbers，thealphabetis{0,1}Otheralphabetsleadtootherbranchingfactors.Oneapplicationfortriesisstoringadictionaryofwords.Trie結(jié)構(gòu)的一個應(yīng)用是存儲字典中的單詞1、TriesAlphabettrieAlphabetconsistsofthe26standardEnglishletters,plusonespecialcharacter($)usedtorepresenttheendofastring.Thus,thebranchingfactorforeachnodeis(upto)27.Alphabettrieacdghnt$elaterr$$$$$$$$ehickeneeuckoeoatldfsish$orsantanteaterantelopechickendeerduckgoatgoldfishgoosehorseAlphabettrieacdghnt$elaeuooalantanteaterantelopechickendeerduckgoatgoldfishgoosehorseExample3.KeyTree又稱數(shù)字查找樹，是一棵度2的樹，樹中的每個結(jié)點(diǎn)中不是包含一個或幾個關(guān)鍵字，而是只含有組成關(guān)鍵字的符號。假設(shè)KEY是數(shù)值，那么結(jié)點(diǎn)中只包含一個數(shù)位假設(shè)KEY是單詞，那么結(jié)點(diǎn)中只包含字母字符例：16個關(guān)鍵字KEY的集合：{CAI,CAO,LI,LAN,CHA,CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,WU,CHEN}首字符不同分成五個子集：{CAI,CAO,CHA,CHANG,CHAO,CHEN}{LI,LAN,LONG,LIU}{WEN,WANG}{YUN,YANG}{ZHAO}集合、子集和元素之間的層次關(guān)系，用一棵樹來表示

----鍵樹Example3.KeyTreeKeyTreeCLWZYAI$0$HAE$NON$G${CAI,CAO,CHA,CHANG,CHAO,CHEN}鍵樹的兩種存儲結(jié)構(gòu)1.以樹的孩子兄弟鏈表示鍵樹

FirstSymbolNext指向兄弟指向第一棵子樹根存儲Key的一個字符CLWAH∧鍵樹的兩種存儲結(jié)構(gòu)2.以樹的多重鏈表表示鍵樹

$ABCD…XYZ$ABCD…H2.BalancedTreesTheBSThasriskofbecomingunbalanced,resultinginexcessivelyexpensivesearchandupdateoperations.Solution:Toadoptanothersearchtreestructuresuchas2-3tree.TomodifytheBSTaccessfunctionsinsomewaytoguaranteethatthetreeperformswell.TheAVLtree:ThesplayTreeTheRed-BlackTree2.BalancedTrees〔1〕TheAVLTreeShouldbeviewedasaBSTwiththefollowingadditionalproperty:Foreverynode,theheightsofitsleftandrightsubtreedifferbyatmost1.Singlerotation:RRrotationLLrotationDoublerotation:RLrotationLRrotation2.BalancedTrees〔2〕TheSplayTreeUnliketheAVLtree,thesplaytreeisnotguaranteedtobeheightbalanced.Whatisguaranteedisthatthetotalcostofallaccesseswillremaincheap.Splaying(展開〕：SinglerotationDoublerotation：zigzagRotationzigzigRotation2.BalancedTrees〔3〕TheRed-BlackTree紅黑樹是一種自平衡二叉查找樹。它的統(tǒng)計(jì)性能要好于平衡二叉樹〔AVL樹〕。紅黑樹在很多地方都有應(yīng)用。在C++STL中，很多局部(目前包括set,multiset,map,multimap)應(yīng)用了紅黑樹的變體(SGISTL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)?？梢栽贠(logn)時(shí)間內(nèi)做查找，插入和刪除等操作。2.BalancedTrees〔3〕TheRed-BlackTree紅黑樹，顧名思義，通過紅黑兩種顏色域保證樹的高度近似平衡。它的每個節(jié)點(diǎn)是一個五元組：color〔顏色〕，key〔數(shù)據(jù)〕，left〔左孩子〕，right〔右孩子〕和p〔父節(jié)點(diǎn)〕。紅黑樹的定義也是它的性質(zhì)，有以下五條：性質(zhì)1.節(jié)點(diǎn)是紅色或黑色性質(zhì)2.根是黑色性質(zhì)3.所有葉子都是黑色〔葉子是NIL節(jié)點(diǎn)〕性質(zhì)4.如果一個節(jié)點(diǎn)是紅的，那么它的兩個兒子都是黑的性質(zhì)5.從任一節(jié)點(diǎn)到其葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。2.BalancedTrees〔3〕TheRed-BlackTree紅黑樹的定義也是它的性質(zhì)，有以下五條：性質(zhì)1.節(jié)點(diǎn)是紅色或黑色性質(zhì)2.根是黑色性質(zhì)3.所有葉子都是黑色〔葉子是NIL節(jié)點(diǎn)〕性質(zhì)4.如果一個節(jié)點(diǎn)是紅的，那么它的兩個兒子都是黑的性質(zhì)5.從任一節(jié)點(diǎn)到其葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。性質(zhì)4暗示著任何一個簡單路徑上不能有兩個毗連的紅色節(jié)點(diǎn)，這樣，最短的可能路徑全是黑色節(jié)點(diǎn)，最長的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。同時(shí)根據(jù)性質(zhì)5知道：所有最長的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，這就說明了沒有路徑能多于任何其他路徑的兩倍長。2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括為以下幾個步驟：(1)查找要插入的位置，時(shí)間復(fù)雜度為：O(N)(2)將新節(jié)點(diǎn)的color賦為紅色(3)自下而上重新調(diào)整該樹為紅黑樹設(shè)要插入的節(jié)點(diǎn)為N，其父節(jié)點(diǎn)為P，其父親G的兄弟節(jié)點(diǎn)為U〔即P和U是同一個節(jié)點(diǎn)的兩個子節(jié)點(diǎn)〕。[1]如果P是黑色的，那么整棵樹不必調(diào)整便是紅黑樹?！瞐〕N的叔叔U是紅色的[2]如果P是紅色的〔可知，其父節(jié)點(diǎn)G一定是黑色的〕，那么插入N后，違背了性質(zhì)4，需要進(jìn)行調(diào)整。調(diào)整時(shí)分以下3種情況：〔b〕N的叔叔U是黑色的，且N是右孩子〔c〕N的叔叔U是黑色的，且N是左孩子2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括為以下幾個步驟：(1)查找要插入的位置，時(shí)間復(fù)雜度為：O(N)(2)將新節(jié)點(diǎn)的color賦為紅色(3)自下而上重新調(diào)整該樹為紅黑樹〔a〕N的叔叔U是紅色的2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括為以下幾個步驟：(1)查找要插入的位置，時(shí)間復(fù)雜度為：O(N)(2)將新節(jié)點(diǎn)的color賦為紅色(3)自下而上重新調(diào)整該樹為紅黑樹〔b〕N的叔叔U是黑色的，且N是右孩子2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括為以下幾個步驟：(1)查找要插入的位置，時(shí)間復(fù)雜度為：O(N)(2)將新節(jié)點(diǎn)的color賦為紅色(3)自下而上重新調(diào)整該樹為紅黑樹〔c〕N的叔叔U是黑色的，且N是左孩子2.BalancedTrees〔3〕TheRed-BlackTree3.2刪除操作刪除操作可以概括為以下幾個步驟：(1)查找要刪除位置，時(shí)間復(fù)雜度為：O(N)(2)用刪除節(jié)點(diǎn)后繼或者節(jié)點(diǎn)替換該節(jié)點(diǎn)〔只進(jìn)行數(shù)據(jù)替換即可，不必調(diào)整指針，后繼節(jié)點(diǎn)是中序遍歷中緊挨著該節(jié)點(diǎn)的節(jié)點(diǎn)，即：右孩子的最左孩子節(jié)點(diǎn)〕(3)如果刪除節(jié)點(diǎn)的替換節(jié)點(diǎn)為黑色，那么需重新調(diào)整該樹為紅黑樹在第(3)步中，如果，如果刪除節(jié)點(diǎn)為紅色節(jié)點(diǎn)，那么他的父親和孩子全為黑節(jié)點(diǎn)，這樣直接刪除該節(jié)點(diǎn)即可，不必進(jìn)行任何調(diào)整。如果刪除節(jié)點(diǎn)是黑節(jié)點(diǎn)，分四種情況：設(shè)要刪除的節(jié)點(diǎn)為N，其父節(jié)點(diǎn)為P，其兄弟節(jié)點(diǎn)為S。由于N是黑色的，那么P可能是黑色的，也可能是紅色的，S也可能是黑色的或者紅色的〔1〕S是紅色的〔2〕S和S的孩子全是黑色的〔3〕S是黑色的，S的左孩子是紅色，右孩子是黑色〔4〕S是黑色的，S的右孩子是紅色搜索引擎的實(shí)現(xiàn)搜索引擎：輸入關(guān)鍵詞，搜索出包含此關(guān)鍵詞的所有網(wǎng)頁實(shí)現(xiàn)方法：將所有網(wǎng)頁全部查找一遍在實(shí)際中不可能用，因?yàn)楹臅r(shí)太多可行的方法：建立關(guān)鍵詞詞典簡易搜索引擎的實(shí)現(xiàn)步驟：〔1〕將文件的內(nèi)容分割成單個的單詞；〔2〕將單詞和對應(yīng)的文件配對參加到一個搜索詞典中，搜索詞典使用AVL樹來實(shí)現(xiàn)；關(guān)鍵：搜索詞典的構(gòu)建分詞〔1〕分詞英文分詞：單個單詞的分割只需要通過空格、TAB符、標(biāo)點(diǎn)符號等便可以實(shí)現(xiàn)中文分詞：所有單詞間沒有任何分隔符號，分詞復(fù)雜，分詞過程：根據(jù)標(biāo)點(diǎn)符號將文章內(nèi)容劃分成句子將句子劃分成詞組或單詞將文章內(nèi)容劃分成句子比較容易將句子劃分成詞組或單詞復(fù)雜基于詞典搜索的簡易分詞算法例：句子“將文章內(nèi)容劃分成句子”分割成單詞：先在詞典中查詢整個句子，如不存在，去掉最右邊一個字，繼續(xù)查詢“將文章內(nèi)容劃分成句”；如果詞典中不存在，再去掉最右邊一個字，繼續(xù)查詢；到最后只剩下一個“將”字時(shí)，不再查詢，得到第一個詞“將”再將句子中已經(jīng)得到的詞“將”去掉，對剩下的“文章內(nèi)容劃分成句子”重復(fù)前面算法，便可以將句子中的單詞或詞組一個個找出來。如果一個句子中有N個單詞或詞組，最壞情況需要進(jìn)行N*(N-1)/2次詞典查詢將單詞或詞組分割〔2〕搜索詞典的構(gòu)建搜索所有的網(wǎng)頁，自動生成關(guān)鍵詞例：有三個網(wǎng)頁File1.htm，F(xiàn)ile2.htm，F(xiàn)ile3.htm，各自包含的內(nèi)容：

File1.htm：Howareyou?File2.htm:Whereareyou?File3.htm:Whereisit?首先搜索第一個文件File1.htm，得到三個關(guān)鍵詞：How、are、you，將關(guān)鍵詞都放在AVL樹中搜索詞典的構(gòu)建HowareyouFile1.htmFile1.htmFile1.htm分詞過程1再搜索File2.htm，也有三個關(guān)鍵詞：Where、are、you，關(guān)鍵詞和文件的對應(yīng)關(guān)系如圖：搜索詞典的構(gòu)建HowareyouFile1.htmFile1.htmFile1.htm分詞過程2WhereFile2.htmFile2.htmFile2.htm繼續(xù)搜索File3.htm，有三個關(guān)鍵詞：Where、is、it，關(guān)鍵詞和文件的對應(yīng)關(guān)系如圖：搜索詞典的構(gòu)建HowFile1.htm分詞過程3WhereFile2.htmareFile1.htmFile2.htmyouFile1.htmFile2.htmisFile3.htmitFile3.htmFile3.htm3.SpacialDataStructure

所有檢索樹：

BSTTheSplaytreeB-treeTries用于檢索一維關(guān)鍵碼多維檢索關(guān)鍵碼如：一個城市記錄數(shù)據(jù)庫City(Name,x,y)BST或伸展樹等對城市Name，或x坐標(biāo)或y坐標(biāo)的檢索提供了很好的性能但只檢索兩個坐標(biāo)〔x,y〕中的一個對于二維空間檢索并不是一種自然的方式坐標(biāo)〔x,y)是二維關(guān)鍵碼給出一個空間位置，空間屬性〔spatialattribute〕3.SpacialDataStructure多維范圍查詢是一個空間應(yīng)用〔spatialapplication〕的重要特性，實(shí)現(xiàn)空間應(yīng)用程序，需要使用空間數(shù)據(jù)結(jié)構(gòu)〔SpatialDataStructure〕，如地理信息系統(tǒng)，計(jì)算機(jī)圖形學(xué)，機(jī)器人學(xué)等。1.空間數(shù)據(jù)及其特征空間數(shù)據(jù)(SpatialData)是指用來表示空間實(shí)體的位置、形狀、大小及其分布特征諸多方面信息的數(shù)據(jù)。它可以用來描述來自現(xiàn)實(shí)世界的目標(biāo)，它具有定位、定性、時(shí)間和空間關(guān)系等特性。1.空間數(shù)據(jù)及其特征空間實(shí)體在空間數(shù)據(jù)中不可再分最小單元現(xiàn)象稱為空間實(shí)體，空間實(shí)體是對存在于這個自然世界中地理實(shí)體的抽象，主要包括點(diǎn)、線、面以及實(shí)體等根本類型：如把一根電線桿抽象成為一個點(diǎn)，該點(diǎn)可以包含電線桿所處的位置信息、電線桿的高度信息和其它一些相關(guān)信息；可以把一條道路抽象為一條線，該線可以包含這條道路的長度、寬度、起點(diǎn)、終點(diǎn)以及道路等級等相關(guān)信息；可以把一個湖泊抽象為一個面，該面可以包含湖泊的周長、面積和湖水的質(zhì)量信息等；“空間關(guān)系”，又稱為“拓?fù)潢P(guān)系”：在空間對象建立后，還可以進(jìn)一步定義其相互之間的關(guān)系，這種相互關(guān)系被稱為“空間關(guān)系”，又稱為“拓?fù)潢P(guān)系”，如可以定義點(diǎn)－線關(guān)系、線－線關(guān)系、點(diǎn)－面關(guān)系等。因此,可以說空間數(shù)據(jù)是一種可以用點(diǎn)、線、面以及實(shí)體等根本空間數(shù)據(jù)結(jié)構(gòu)來表示人們賴以生存的自然世界的數(shù)據(jù)。1.空間數(shù)據(jù)及其特征空間數(shù)據(jù)被視為一種特殊的數(shù)據(jù)，它們具有要求用非標(biāo)準(zhǔn)數(shù)據(jù)庫管理方法的幾個特點(diǎn)：空間對象結(jié)構(gòu)的復(fù)雜性。比方一個簡單的點(diǎn)或一組任意分布的多邊形，都是空間數(shù)據(jù)對象。有固定長度的關(guān)聯(lián)數(shù)據(jù)庫元組不適合存儲這樣的數(shù)據(jù)格式?？臻g數(shù)據(jù)的動態(tài)性。這種特點(diǎn)要求能數(shù)據(jù)結(jié)構(gòu)能適應(yīng)頻繁地插入、刪除以及更新對象。空間數(shù)據(jù)庫不斷增長。在地理地圖或者VLSI電路的對象數(shù)目往往需要千兆字節(jié)的存儲空間。沒有空間代數(shù)標(biāo)準(zhǔn)。它們通常根據(jù)特定空間數(shù)據(jù)庫的應(yīng)用領(lǐng)域來決定空間操作?？臻g操作不封閉。如兩個空間對象的交集可能是一組點(diǎn)、線或區(qū)域?？臻g數(shù)據(jù)的多維性。該特性使傳統(tǒng)數(shù)據(jù)庫索引方法〔如B樹或線性散列法〕不適合索引空間數(shù)據(jù)。2.空間數(shù)據(jù)結(jié)構(gòu)的應(yīng)用場合

空間數(shù)據(jù)是數(shù)字地球的根底信息,數(shù)字地球功能的絕大局部將以空間數(shù)據(jù)為根底?，F(xiàn)在空間數(shù)據(jù)已廣泛應(yīng)用于社會各行業(yè)、各部門，如城市規(guī)劃、交通、銀行、航空航天等。隨著科學(xué)和社會的開展，人們已經(jīng)越來越認(rèn)識到空間數(shù)據(jù)對于社會經(jīng)濟(jì)的開展、人們生活水平提高的重要性，這也加快了人們獲取和應(yīng)用空間數(shù)據(jù)的步伐。2.空間數(shù)據(jù)結(jié)構(gòu)的應(yīng)用場合

數(shù)字化城市GIS：用于一個兩維的空間存儲對象，對象可能是點(diǎn)或形狀－－這個數(shù)據(jù)庫是地圖，其中存儲的對象可能表示房子、路、橋、管道等VLSI集成電路設(shè)計(jì):“幅員”(層、(x,y))數(shù)據(jù)立方體：許多公司為了決策支持應(yīng)用而收集的多維數(shù)據(jù)

如：一個連鎖店可以記錄每一筆銷售銷售〔日期和時(shí)間，銷售所屬的商店，購置的商品，商品的顏色、大小〕適合數(shù)據(jù)立方體的數(shù)據(jù)經(jīng)常組織成一個事實(shí)表和假設(shè)干維表事實(shí)表給出被記錄的根本元素〔如每筆銷售〕sales(day,store,item,color,size)維表給出每一維的屬性值的特征，如銷售所屬的商店是一維，包括〔地址、、商店經(jīng)理等〕store(Add,Tel,Manager)3.查詢點(diǎn)查詢?nèi)缱鴺?biāo)〔x,y〕是什么城市？范圍查詢〔區(qū)域查詢〕二維范圍查詢：如檢索在一個指定點(diǎn)的給定范圍內(nèi)的所有城市最鄰近查詢?nèi)缗c坐標(biāo)〔x,y〕最近的城市？3.查詢?nèi)纾轰N售〔日期和時(shí)間，銷售所屬的商店，購置的商品，商品的顏色、大小〕事實(shí)表：每筆銷售sales(day,store,item,color,size)維表：商店store(Add,Tel,Manager)查詢：按日期和商店匯總粉紅色襯衫的銷售

selectdaystorecount(*)AstotalSalesFormsalesWhereitem=’shirt’ANDcolor=’pink’Groupbyday,store;

——通過日期和商店這二維來分組組織銷售，利用Count聚集操作符匯總其他維的情況。Where子句選擇粉紅襯衫的元組。4.空間數(shù)據(jù)結(jié)構(gòu)⑴使用傳統(tǒng)索引技術(shù)執(zhí)行范圍查詢假定有兩維〔x,y〕：給x和y這兩維中的每一維都建立一個輔助索引——B+樹給定兩維的范圍，首先通過x的B樹索引得到在x范圍內(nèi)所有記錄的指針,然后再通過y的B樹索引得到在y范圍內(nèi)的所有記錄指針再求出這些指針的交集⑵多維索引結(jié)構(gòu)支持多維數(shù)據(jù)查詢的數(shù)據(jù)結(jié)構(gòu)歸于兩類：類散列表的方法：網(wǎng)格文件，分段散列函數(shù)類樹方法〔k-d樹，PD四分樹，R樹等〕盡管對空間數(shù)據(jù)表的研究歷史以有20多年，但迄今仍沒有哪一種空間數(shù)據(jù)結(jié)構(gòu)被公認(rèn)是最好的4.空間數(shù)據(jù)結(jié)構(gòu)K-d樹PR四分樹R樹BST向多維的自然擴(kuò)展