树的四种分类

《树的四种分类》由会员分享，可在线阅读，更多相关《树的四种分类（15页珍藏版）》请在金锄头文库上搜索。

1、SearchSearch treestrees：实例：实例-二叉搜索树二叉搜索树 什么是二叉搜索树 二叉搜索树(Binary Search Tree)是一棵有序的二叉树，所以我们也可以称它为二叉排 序树（不知道二叉树的童鞋，先看看二叉树：传送门）。 具有以下性质的二叉树我们称之为二叉搜索树： 若它的左子树不为空， 那么左子树上的 所有值均小于它的根节点；若它的右子树不为空，那么右子树上所有值均大于它的根节点。 它的左子树和右子树分别也为二叉搜索树。 2、二叉搜索树的结构 二叉搜索树能够高效的进行一下操作： 插入一个数值查询是否包含某个数值删除 某个数值 根据实现的不同，还可以实现其他各种操作，

2、这是一种使用性很高的数据结构。我们来 看一个例子： 这就是二叉搜索树的存储结构，所有的节点，都满足左子树上的比自己小，而右子树上 的所有节点比自己大。二叉搜索树因为其有序性，所以它能够高效的管理数的集合 (1)查询 我们查找是否存在 17： 根节点是 7，因为小于 17，所以去右子树查找 走到节点 12，还是小于 17，所以继续往右子树找 走到节点 17，此时找到 17。 (2)插入 我们使用查找的方式进行插入，以数字 6 为例，如图所示： (3)删除 删除操作相对之前的其他两种操作， 就略显复杂一些。 一般来说我们可以分为三种情 况： 需要删除的节点没有左儿子，那么就把右儿子提上去 需要删除

3、的节点的左儿子没有右儿子，那么就把左儿子提上去 不满足上述的两种情况的话，就把左子树中最大的节点放到要删除的节点上。 3、二叉搜索树的复杂度 无论我们执行哪一个操作，其所花的时间都和树的高度成正比。我们不难得知，二叉搜 索树的平均复杂度为 O(log n)。 4、二叉搜索树的实现 通过上述的了解， 我们大致已经知道二叉搜索树的工作原理。 所以现在我们就来简单的 实现二叉搜索树基本的增删查的功能，代码如下： cppview plaincopy 1./表示节点的结构体 2.structnode 3.intval; 4.node*lch,*rch; 5.; 6./插入整数 x 7.node*inse

4、rt(node*p,intx) 8.if(p=NULL) 9.node*newNode=newnode; 10.newNode-val=x; 11.newNode-lch=newNode-rch=NULL; 12.p=newNode; 13.else 14.if(xval)p-lch=insert(p-lch,x); 15.elsep-rch=insert(p-rch,x); 16. 17.returnp; 18. 19./查找整数 x 20.boolfind(node*p,intx) 21.if(p=NULL)returnfalse; 22.elseif(p-val=x)returntrue

5、; 23.elseif(p-valx)returnfind(p-lch,x); 24.elsereturnfind(p-rch,x); 25. 26./删除整数 x 27.node*remove(node*p,intx) 28.if(p=NULL)returnNULL; 29.elseif(xval)p-lch=remove(p-lch,x); 30.elseif(xp-val)p-rch=remove(p-rch,x); 31./情况 32.elseif(p-lch=NULL) 33.node*q=p-rch; 34.deletep; 35.returnq; 36. 37./情况 38.el

6、seif(p-lch-rch=NULL) 39.node*q=p-lch; 40.q-rch=p-rch; 41.deletep; 42.returnq; 43. 44./情况 45.else 46.node*q; 47.for(q=p-lch;q-rch-rch!=NULL;q=q-rch); 48.node*r=q-rch; 49.q-rch=r-lch; 50.r-lch=p-lch; 51.r-rch=p-rch; 52.deletep; 53.returnr; 54. 55.returnp; 56. HeapsHeaps；实例；实例-斐波那契堆斐波那契堆 斐波纳契堆 （Fibonac

7、ci Heap） 于 1984 年由 Michael L. Fredman 与 Robert E. Tarjan 提出，1987 年公开发表，名字来源于运行时分析所使用的斐波那契数。 斐波那契堆同二项堆（Binomial Heap）一样，也是一种可合并堆（Mergeable Heap）。 与二项堆一样，斐波那契堆是由一组最小堆有序树构成，但堆中的树并不一定是二项树。与 二项堆中树都是有序的不同，斐波那契堆中的树都是有根而无序的。 特点： 不涉及删除元素的操作有 O(1)的平摊时间。 Extract-Min 和 Delete 的数目和其它相 比较小时效率更佳。关键思想在于尽量延迟对堆的维护 稠密

8、图每次 Decreasekey 只要 O(1)的平摊时间，和二项堆的 O(lgn)相比是巨大的改 进。 斐波那契堆的结构较二项堆更松散。因此对结构的维护可以到方便时再做。 斐波那契堆中的树是有根而无序的。每个节点包含一个指向其父节点的指针 px，以 及一个指向其任一子女的指针 childx（指向子女双链表）。 每个孩子有 leftx和 rightx。 （意义： 在 O(1)的时间内去掉一个节点， 或者在 O(1) 的时间内合并双链表。）其它域： degreex存储子女个数。 markx指示自从 x 上一次成 为另一节点的子女以来，它是否失掉一个孩子。 一个给定的斐波那契堆可以通过一个指向其含有

9、最小关键字树的指针来访问。 斐波那契堆的关键思想在于尽量延迟对堆的维护。创建一个新的斐波那契堆： MAKE_Fib_Heap 有 O(1)的代价。 插入一个节点：分三步进行： 1，为新的节点置 p，child，left，right，mark 等域。 时间消耗： O(1)。 2，将包含 x 的根表和根表 H 连接。时间消耗： O(1) 。3，在 O(1)的 时间内调整指向该堆的指针 minx 时间消耗： O(1) 。以节点数表示势。势的增加为 1， 实际代价为 O(1)。所以平摊代价为 O(1)。 寻找最小节点： minx指向的节点即为最小节点。因为势没有变化，所以这个操作的 平摊代价为 O(1

10、)。 合并两个斐波那契堆：分为 3 步： 1。合并根表 2。设置新的 minh 3。重置 nx。 抽取最小节点：这是最复杂的工作。被延迟的对根表的调整工作最终由这个操作进行。 1。去掉最小值，将其每个孩子都加入根表。 2。将相同度数树的合并。 调整根表的步骤 1。 在根表中找出两个具有相同度数的根 x 和 y， 且 keyx keyy 2。 将 y 与 x 连接。将 y 从根表里去掉，成为 x 一个孩子，并增加 degreex。 减小一个节点的权 1。若此减小不影响堆序，不作调整。 2。若影响堆序，则从堆中删 除该节点，将其加入根表。并检查其父亲的 mark 位。 若为 false，则停止，并

11、将其置为 true。若为 true，则删除其父亲，继续递归向上执 行。直到一个 节点 mark 域为 false 或该节点为根节点为止。 删除一个节点： 1。将该节点权调整至最小 2。抽取最小值。 证明最大度数界：证明删除或 extractmin 的平摊时间为 O（lgn)。引理 1：设 x 为斐 波那契堆中任一节点，并假设 degreex=k。设 y1，y2，。yk 表示按与 x 链接的次序 排列的 x 的子女，从最早的到最迟的，则对 i=2,3,.,k，有 degreey1=0 且 degreeyi=i-2 证明：显然 degreey1=0 对 i=2，注意到 y1 被链接到 x 上时，y

12、1， y2，。yi1 都是 x 的子女，故我们必有 degreex=i-1 又仅当 degreex=degreeyi 时，才将 yi 链接到 x 上。故此时必有 degreeyi=i-1，在此之后，节点 yi 至多失去一个 孩子，因为失去两个就被切断了。所以 degreeyi=i-2 引理 2：对所有的整数 k=0，Fk+2=1+sum（Fi） 0= Gk ，其中 G 为黄金分割率。 (1+50.5)/2=1.161803. 引理 3： 设 x 为斐波那契堆中任一节点， 并设 k=degreex， 那么， size(x)=Fk+2=Gk。 推论：在一个包含 n 个节点的斐波那契堆中节点的最大度

13、数为 O(lgn)。 实际上， 斐波那契堆松散地基于二项堆。 如果不对斐波那契堆做任何 DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样。但是如果执行这两种操作，在一些状态下必 须要破坏二项树的特征，比如 DECREASE-KEY 或 DELETE 后，有的树高为 k，但是结点个数 却少于 2k。这种情况下，堆中的树不是二项树。 斐波那契堆的优势是：不涉及删除元素的操作仅需要 O(1) 的平摊运行时间。 Operation BinaryBinomialFibonacci PairingBrodalRank-pairing find-min(1)(1)(1)(1)(1

14、)(1) delete-min(logn)(logn) O(logn) O(logn) O(logn) O(logn) insert(logn) (1) (1)(1)(1)(1) decrease-key (logn)(logn) (1)Unknown (1) (1) merge (mlog(n+m) O(logn) (1)(1)(1)(1) 对于斐波那契堆上的各种可合并操作，关键思想是尽可能久地将工作推后。例如，当向 斐波那契堆中插入新结点或合并两个斐波那契堆时，并不去合并树，而是将这个工作留给 EXTRACT-MIN 操作 SpatialSpatial datadata partition

15、ingpartitioning treestrees：实例：实例-Burkhard-KellerBurkhard-Keller 树树 BK 树或者称为 Burkhard-Keller 树，是一种基于树的数据结构，被设计于快速查找近 似字符串匹配， 比方说拼写检查器， 或模糊查找， 当搜索” aeek” 时能返回” seek” 和” peek” 。 为何 BK-Trees 这么酷，因为除了穷举搜索，没有其他显而易见的解决方法，并且它能以简 单和优雅的方法大幅度提升搜索速度。 在定义 BK 树之前，我们需要预先定义一些操作。为了索引和搜索字典，我们需要一种 比较字符串的方法。编辑距离（Levens

16、htein Distance）是一种标准的方法，它用来表示 经过插入、 删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数。 其它字符 串函数也同样可接受（比如将调换作为原子操作），只要能满足以下一些条件。 除了字符串匹配、查找回文串、查找重复子串等经典问题以外，日常生活中我们还会 遇到其它一些怪异的字符串问题。比如，有时我们需要知道给定的两个字符串“有多像”， 换句话说两个字符串的相似度是多少。1965 年，俄国科学家 Vladimir Levenshtein 给字符 串相似度做出了一个明确的定义叫做 Levenshtein 距离，我们通常叫它“编辑距离”。字符 串 A 到 B 的编辑距离是指，只用插入、删除和替换三种操作，最少需要多少步可以把 A 变成 B。例如，从 FAME 到 GATE 需要两步（两次替换），从 GA