数据结构之树

数据结构之树二叉检索树二叉检索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉检索树。二叉检索树的基本操作插入在二叉检索树中插入新结点，要保证插入新结点后仍能满足二叉检索树的性质。a、若二叉检索树root为空，则使新结点为根；

b、若二叉检索树root不为空，就要先和根结点的关键字作比较，如果比根结点的值小，就插入到根结点的左子树中，如果比根结点的值大就插入到根结点的右子树中，如此递归下去，找到插入的位置。

c、若新结点的关键字小于插入点的关键字，则将新结点插入到插入点的左子树中，大于则插入到插入点的右子树中。二叉检索树的基本操作查找

查找的功能和插入差不多一样，按照插入那样的方式递归下去，如果找到了，就返回这个节点的地址，如果没有找到，就返回NULL。template<classT>TreeNode<T>*BST<T>::findpri(TreeNode<T>*node,Tx){if(node==NULL)//如果结点为空说明没找到,返回NULL{returnNULL;}if(node->data>x)//如果x小于结点的值,就继续在结点的左子树中查找x{returnfindpri(node->pLChid,x);}elseif(node->data<x){returnfindpri(node->pRChild,x);}elsereturnnode;//如果相等,就找到了此结点}二叉检索树的基本操作删除二叉检索树的删除，分三种情况进行处理：1.p为叶子结点，直接删除该结点，再修改其父结点的指针（注意分是根结点和不是根结点），如图a。

2.p为单支结点（即只有左子树或右子树）。让p的子树与p的父结点相连，删除p即可；（注意分是根节点和不是根节点）；如图b二叉检索树的基本操作3.P是左右都有孩子的结点，有一个著名的算法HubbardDeletion。删除策略是用其右子树最小的数据代替该结点的数据并递归的删除掉右子树中最小数据的结点。因为右子树中数据最小的结点肯定没有左孩子，所以删除的时候容易一些。如右图所示，删除结点2。堆树堆树的定义如下：（1）堆树是一颗完全二叉树；（2）堆树中某个结点的值总是不大于或不小于其孩子结点的值；（3）堆树中每个结点的子树都是堆树。当父结点的键值总是大于或等于任何一个子结点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子结点的键值时为最小堆。如右图所示，上边为最大堆，下边为最小堆。构造最大堆构造最大堆在构造堆的基本思想就是：首先将每个叶子结点视为一个堆，再将每个叶子结点与其父结点一起构造成一个包含更多结点的对。所以，在构造堆的时候，首先需要找到最后一个结点的父结点，从这个结点开始构造最大堆；直到该结点前面所有分支结点都处理完毕，这样最大堆就构造完毕了。堆树的基本操作插入（以最小堆为例）1.将新的元素插入到树中，先直接插入使之成为叶子结点，同时保证该树依然是完全二叉树。若该元素大于其父结点，两个元素互换。（上移操作）3.循环第2步，直至该元素没有父结点或小于其父结点。堆树的基本操作

删除（从最小堆1017203038302434）删除元素则是按照添加元素相反的方向来做，我们需要删除的元素是堆顶，在这里是最小的那一个元素10，接着我们将最后一位元素放到堆顶的位置（之前的元素已经删除了，所以这里空了一个位置），得到下图：34

172030383024现在我们将比较堆顶的新元素与他的子节点，如果堆顶新元素比他的子节点都要大，则将新的堆顶元素与子节点中较小的元素交换。在这里堆顶元素为34，他的子节点分别在位置（1*2=2）和（1*2+1=3），即为17和20，34要大于17和20，所以我们将34与17（子节点中较小的一个）交换，得到下图：17

34

2030383024

接着我们得到34当前所在位置为2（从1开始数），那么他的子节点位置分别为（2*2=4）和（2*2+1=5），即为30和38，由于34还是大于他的所有子节点，交换34与20（子节点中较小的），得到下图：173020

34

383024

当前34所在位置为4，子节点位置（4*2=8）和（4*2+1=9），由于当前堆的最大长度为7，小于8和9，没有元素与之对应，所以到这里元素删除完毕。1017302024303834341730202430381734302024303817303420243038字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。Trie树的基本性质可以归纳为：（1）根结点不包含字符，除根结点以外每个结点只包含一个字符。（2）从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。（3）每个结点的所有子结点包含的字符串不相同。(4)插入和查找的时间复杂度为O(n),n为字符串长度。

字典树的基本操作插入对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。假设以英文单词构建的字典树为例，这棵Trie树中每个结点包括26个孩子结点，因为总共有26个英文字母(假设单词都是小写字母组成)。字典树的基本操作查找(1)每次从根结点开始一次搜索；(2)取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；(3)在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。(4)迭代过程……

(5)在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

字典树的应用1.字典树在串的快速检索中的应用。给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中先把熟词建一棵字典树，然后读入文章进行比较，这种方法效率是比较高的。2.字典树在“串”排序方面的应用给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可3.字典树在最长公共前缀问题的应用对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为最近公共祖先问题。R树一棵R树满足如下的性质：1.除非它是根结点之外，所有叶子结点包含有m至M个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于m。通常，m=M/2。2.对于所有在叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。3.每一个飞叶子结点拥有m至M个孩子结点，除非它是根结点。4.对于在非叶子结点上的每一个条目，i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形（同性质2）。5.所有叶子结点都位于同一层，因此R树为平衡树R树的作用R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子吧：查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌地图这种超大数据库中，我想这种方法肯定不可行吧。R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。R树的数据结构R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满