高等数据结构与算法分析4

Chapter3

AdvancedTreeStructuresThischapterintroducesseveraltreestructuresdesignedforuseinspecializedapplications.

1.Tries2.BalancedTrees3.SpatialDataStructures1.Tries2.BalancedTrees3.SpatialDataStructuresiscommanlyusedtostorestringsandissuitableforstoringandsearchingcollectionsofstrings.用于存储字符串，适合于字典的存储和检索arevariantsontheBST.Theyareexamplesofself-balancingsearchtreesandhaveguaranteedgoodperformanceregardlessoftheinsertionorderforrecords.BST的变体，是自平衡检索树Usedtoorganizepointdatabyxy-coordinates.1、TriesThedatastructurebasedonObjectSpacedecomposition

基于对象空间分解的数据结构

TheshapeofaBSTdependsontheorderinwhichitsdatarecordsareinserted.BST的形状依赖于数据记录插入顺序TheresultingBSTmightbebalancedorunbalanced.----thedecompositionofthekeyrangeisdrivenbytheobjectsstoredinthetree.关键码范围的分解是由存储在树中的对象驱动的ThedatastructurebasedonKeySpacedecomposition

基于关键码空间分解的数据结构

1、TriesThedatastructurebasedonObjectSpacedecomposition

基于对象空间分解的数据结构ThedatastructurebasedonKeySpacedecomposition

基于关键码空间分解的数据结构

Topredefinethesplittingpositionwithinthesplittingpositionwithinthekeyrangeforeachnodeinthetree.Inotherwords,therootcouldbepredefinedtosplitthekeyrangeintotwoequalhalves.,regardlessoftheparticularvaluesororderofinsertionforthedatarecords.对树结构中每一结点在关键码范围预定义划分位置。也就是说，应当预定义根结点，把关键码范围划分成相等的两半，而不管数据记录的具体值或者插入顺序。Decompositionbasedonequalsubdivisionofthekeyrangeiscalledkeyspacedecomposition.基于关键码范围相等子划分的分解称为关键码空间分解称为一个Trie结构LiketheB＋-tree，atriestoresdatarecordsonlyinleafnodes.Internalnodesserveasplaceholderstodirectthesearchprocess.Trie结构只在叶结点存储数据记录，内部结点只作占位符占据位置，并引导检索过程。Example1.Thebinarytrieforthesetofvalues〔2，7，24，32，37，40，42，120〕Example

2.Huffmancodingtree1、TriesBinaryTriesForbinarynumbers，thealphabetis{0,1}Otheralphabetsleadtootherbranchingfactors.Oneapplicationfortriesisstoringadictionaryofwords.Trie结构的一个应用是存储字典中的单词1、TriesAlphabettrieAlphabetconsistsofthe26standardEnglishletters,plusonespecialcharacter($)usedtorepresenttheendofastring.Thus,thebranchingfactorforeachnodeis(upto)27.Alphabettrieacdghnt$elaterr$$$$$$$$ehickeneeuckoeoatldfsish$orsantanteaterantelopechickendeerduckgoatgoldfishgoosehorseAlphabettrieacdghnt$elaeuooalantanteaterantelopechickendeerduckgoatgoldfishgoosehorseExample3.KeyTree又称数字查找树，是一棵度2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。假设KEY是数值，那么结点中只包含一个数位假设KEY是单词，那么结点中只包含字母字符例：16个关键字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}集合、子集和元素之间的层次关系，用一棵树来表示

----键树Example3.KeyTreeKeyTreeCLWZYAI$0$HAE$NON$G${CAI,CAO,CHA,CHANG,CHAO,CHEN}键树的两种存储结构1.以树的孩子兄弟链表示键树

FirstSymbolNext指向兄弟指向第一棵子树根存储Key的一个字符CLWAH∧键树的两种存储结构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红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树〔AVL树〕。红黑树在很多地方都有应用。在C++STL中，很多局部(目前包括set,multiset,map,multimap)应用了红黑树的变体(SGISTL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。可以在O(logn)时间内做查找，插入和删除等操作。2.BalancedTrees〔3〕TheRed-BlackTree红黑树，顾名思义，通过红黑两种颜色域保证树的高度近似平衡。它的每个节点是一个五元组：color〔颜色〕，key〔数据〕，left〔左孩子〕，right〔右孩子〕和p〔父节点〕。红黑树的定义也是它的性质，有以下五条：性质1.节点是红色或黑色性质2.根是黑色性质3.所有叶子都是黑色〔叶子是NIL节点〕性质4.如果一个节点是红的，那么它的两个儿子都是黑的性质5.从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。2.BalancedTrees〔3〕TheRed-BlackTree红黑树的定义也是它的性质，有以下五条：性质1.节点是红色或黑色性质2.根是黑色性质3.所有叶子都是黑色〔叶子是NIL节点〕性质4.如果一个节点是红的，那么它的两个儿子都是黑的性质5.从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。性质4暗示着任何一个简单路径上不能有两个毗连的红色节点，这样，最短的可能路径全是黑色节点，最长的可能路径有交替的红色和黑色节点。同时根据性质5知道：所有最长的路径都有相同数目的黑色节点，这就说明了没有路径能多于任何其他路径的两倍长。2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括为以下几个步骤：(1)查找要插入的位置，时间复杂度为：O(N)(2)将新节点的color赋为红色(3)自下而上重新调整该树为红黑树设要插入的节点为N，其父节点为P，其父亲G的兄弟节点为U〔即P和U是同一个节点的两个子节点〕。[1]如果P是黑色的，那么整棵树不必调整便是红黑树。〔a〕N的叔叔U是红色的[2]如果P是红色的〔可知，其父节点G一定是黑色的〕，那么插入N后，违背了性质4，需要进行调整。调整时分以下3种情况：〔b〕N的叔叔U是黑色的，且N是右孩子〔c〕N的叔叔U是黑色的，且N是左孩子2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括为以下几个步骤：(1)查找要插入的位置，时间复杂度为：O(N)(2)将新节点的color赋为红色(3)自下而上重新调整该树为红黑树〔a〕N的叔叔U是红色的2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括为以下几个步骤：(1)查找要插入的位置，时间复杂度为：O(N)(2)将新节点的color赋为红色(3)自下而上重新调整该树为红黑树〔b〕N的叔叔U是黑色的，且N是右孩子2.BalancedTrees〔3〕TheRed-BlackTree3.1插入操作插入操作可以概括为以下几个步骤：(1)查找要插入的位置，时间复杂度为：O(N)(2)将新节点的color赋为红色(3)自下而上重新调整该树为红黑树〔c〕N的叔叔U是黑色的，且N是左孩子2.BalancedTrees〔3〕TheRed-BlackTree3.2删除操作删除操作可以概括为以下几个步骤：(1)查找要删除位置，时间复杂度为：O(N)(2)用删除节点后继或者节点替换该节点〔只进行数据替换即可，不必调整指针，后继节点是中序遍历中紧挨着该节点的节点，即：右孩子的最左孩子节点〕(3)如果删除节点的替换节点为黑色，那么需重新调整该树为红黑树在第(3)步中，如果，如果删除节点为红色节点，那么他的父亲和孩子全为黑节点，这样直接删除该节点即可，不必进行任何调整。如果删除节点是黑节点，分四种情况：设要删除的节点为N，其父节点为P，其兄弟节点为S。由于N是黑色的，那么P可能是黑色的，也可能是红色的，S也可能是黑色的或者红色的〔1〕S是红色的〔2〕S和S的孩子全是黑色的〔3〕S是黑色的，S的左孩子是红色，右孩子是黑色〔4〕S是黑色的，S的右孩子是红色搜索引擎的实现搜索引擎：输入关键词，搜索出包含此关键词的所有网页实现方法：将所有网页全部查找一遍在实际中不可能用，因为耗时太多可行的方法：建立关键词词典简易搜索引擎的实现步骤：〔1〕将文件的内容分割成单个的单词；〔2〕将单词和对应的文件配对参加到一个搜索词典中，搜索词典使用AVL树来实现；关键：搜索词典的构建分词〔1〕分词英文分词：单个单词的分割只需要通过空格、TAB符、标点符号等便可以实现中文分词：所有单词间没有任何分隔符号，分词复杂，分词过程：根据标点符号将文章内容划分成句子将句子划分成词组或单词将文章内容划分成句子比较容易将句子划分成词组或单词复杂基于词典搜索的简易分词算法例：句子“将文章内容划分成句子”分割成单词：先在词典中查询整个句子，如不存在，去掉最右边一个字，继续查询“将文章内容划分成句”；如果词典中不存在，再去掉最右边一个字，继续查询；到最后只剩下一个“将”字时，不再查询，得到第一个词“将”再将句子中已经得到的词“将”去掉，对剩下的“文章内容划分成句子”重复前面算法，便可以将句子中的单词或词组一个个找出来。如果一个句子中有N个单词或词组，最坏情况需要进行N*(N-1)/2次词典查询将单词或词组分割〔2〕搜索词典的构建搜索所有的网页，自动生成关键词例：有三个网页File1.htm，File2.htm，File3.htm，各自包含的内容：

File1.htm：Howareyou?File2.htm:Whereareyou?File3.htm:Whereisit?首先搜索第一个文件File1.htm，得到三个关键词：How、are、you，将关键词都放在AVL树中搜索词典的构建HowareyouFile1.htmFile1.htmFile1.htm分词过程1再搜索File2.htm，也有三个关键词：Where、are、you，关键词和文件的对应关系如图：搜索词典的构建HowareyouFile1.htmFile1.htmFile1.htm分词过程2WhereFile2.htmFile2.htmFile2.htm继续搜索File3.htm，有三个关键词：Where、is、it，关键词和文件的对应关系如图：搜索词典的构建HowFile1.htm分词过程3WhereFile2.htmareFile1.htmFile2.htmyouFile1.htmFile2.htmisFile3.htmitFile3.htmFile3.htm3.SpacialDataStructure

所有检索树：

BSTTheSplaytreeB-treeTries用于检索一维关键码多维检索关键码如：一个城市记录数据库City(Name,x,y)BST或伸展树等对城市Name，或x坐标或y坐标的检索提供了很好的性能但只检索两个坐标〔x,y〕中的一个对于二维空间检索并不是一种自然的方式坐标〔x,y)是二维关键码给出一个空间位置，空间属性〔spatialattribute〕3.SpacialDataStructure多维范围查询是一个空间应用〔spatialapplication〕的重要特性，实现空间应用程序，需要使用空间数据结构〔SpatialDataStructure〕，如地理信息系统，计算机图形学，机器人学等。1.空间数据及其特征空间数据(SpatialData)是指用来表示空间实体的位置、形状、大小及其分布特征诸多方面信息的数据。它可以用来描述来自现实世界的目标，它具有定位、定性、时间和空间关系等特性。1.空间数据及其特征空间实体在空间数据中不可再分最小单元现象称为空间实体，空间实体是对存在于这个自然世界中地理实体的抽象，主要包括点、线、面以及实体等根本类型：如把一根电线杆抽象成为一个点，该点可以包含电线杆所处的位置信息、电线杆的高度信息和其它一些相关信息；可以把一条道路抽象为一条线，该线可以包含这条道路的长度、宽度、起点、终点以及道路等级等相关信息；可以把一个湖泊抽象为一个面，该面可以包含湖泊的周长、面积和湖水的质量信息等；“空间关系”，又称为“拓扑关系”：在空间对象建立后，还可以进一步定义其相互之间的关系，这种相互关系被称为“空间关系”，又称为“拓扑关系”，如可以定义点－线关系、线－线关系、点－面关系等。因此,可以说空间数据是一种可以用点、线、面以及实体等根本空间数据结构来表示人们赖以生存的自然世界的数据。1.空间数据及其特征空间数据被视为一种特殊的数据，它们具有要求用非标准数据库管理方法的几个特点：空间对象结构的复杂性。比方一个简单的点或一组任意分布的多边形，都是空间数据对象。有固定长度的关联数据库元组不适合存储这样的数据格式。空间数据的动态性。这种特点要求能数据结构能适应频繁地插入、删除以及更新对象。空间数据库不断增长。在地理地图或者VLSI电路的对象数目往往需要千兆字节的存储空间。没有空间代数标准。它们通常根据特定空间数据库的应用领域来决定空间操作。空间操作不封闭。如两个空间对象的交集可能是一组点、线或区域。空间数据的多维性。该特性使传统数据库索引方法〔如B树或线性散列法〕不适合索引空间数据。2.空间数据结构的应用场合

空间数据是数字地球的根底信息,数字地球功能的绝大局部将以空间数据为根底。现在空间数据已广泛应用于社会各行业、各部门，如城市规划、交通、银行、航空航天等。随着科学和社会的开展，人们已经越来越认识到空间数据对于社会经济的开展、人们生活水平提高的重要性，这也加快了人们获取和应用空间数据的步伐。2.空间数据结构的应用场合

数字化城市GIS：用于一个两维的空间存储对象，对象可能是点或形状－－这个数据库是地图，其中存储的对象可能表示房子、路、桥、管道等VLSI集成电路设计:“幅员”(层、(x,y))数据立方体：许多公司为了决策支持应用而收集的多维数据

如：一个连锁店可以记录每一笔销售销售〔日期和时间，销售所属的商店，购置的商品，商品的颜色、大小〕适合数据立方体的数据经常组织成一个事实表和假设干维表事实表给出被记录的根本元素〔如每笔销售〕sales(day,store,item,color,size)维表给出每一维的属性值的特征，如销售所属的商店是一维，包括〔地址、、商店经理等〕store(Add,Tel,Manager)3.查询点查询如坐标〔x,y〕是什么城市？范围查询〔区域查询〕二维范围查询：如检索在一个指定点的给定范围内的所有城市最邻近查询如与坐标〔x,y〕最近的城市？3.查询如：销售〔日期和时间，销售所属的商店，购置的商品，商品的颜色、大小〕事实表：每笔销售sales(day,store,item,color,size)维表：商店store(Add,Tel,Manager)查询：按日期和商店汇总粉红色衬衫的销售

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

——通过日期和商店这二维来分组组织销售，利用Count聚集操作符汇总其他维的情况。Where子句选择粉红衬衫的元组。4.空间数据结构⑴使用传统索引技术执行范围查询假定有两维〔x,y〕：给x和y这两维中的每一维都建立一个辅助索引——B+树给定两维的范围，首先通过x的B树索引得到在x范围内所有记录的指针,然后再通过y的B树索引得到在y范围内的所有记录指针再求出这些指针的交集⑵多维索引结构支持多维数据查询的数据结构归于两类：类散列表的方法：网格文件，分段散列函数类树方法〔k-d树，PD四分树，R树等〕尽管对空间数据表的研究历史以有20多年，但迄今仍没有哪一种空间数据结构被公认是最好的4.空间数据结构K-d树PR四分树R树BST向多维的自然扩展