- 浏览: 405786 次
文章分类
最新评论
-
lvdccyb:
wuhan_liurui 写道安装这种配置并没有成功,上面说的 ...
Spring Cloud (1)——config server使用SVN作为远程例子的运行与配置 -
wuhan_liurui:
安装这种配置并没有成功,上面说的,需要仔细阅读spring 官 ...
Spring Cloud (1)——config server使用SVN作为远程例子的运行与配置 -
g_man1990:
maven clean后无法生成。class文件
设置JAVA编译程序级别,Maven编译插件(翻译)--(2) -
最佳蜗牛:
非常感谢,我也遇到这个问题,用楼主的方法解决问题了。
Hadoop HDFS配置——UnknownHostException -
mousepc:
今天被这个问题害了...
JAVA时间的一个陷阱
扩展树的C语言实现版本,这个是自上而下且节点带大小(size)的扩展树(伸展树)的具体实现。它由Daniel Dominic Sleator 和Robert Endre Tarjan,Tarjan在计算机算法领域,是个大师级别的人物,求强连通图的分量scc算法,很多基础的算法都是他发现的一个扩展树是自适应调整的二叉搜索树。其他常见的二叉搜索树有,AVL tree,red-black tree(红黑树)。但这里有个明显的区别,splay tree 通过节点额外附带属性信息,该信息记录最近访问的节点。它提供基本操作,如插入,查询和删除,平摊情况下都是 O(logN)的渐近复杂度,单次操作,要比,要对于非随机访问操作,splay tree,即使在不知道访问序列的具体模式情况下,也比其他搜索树提供较好性能。二叉搜索树上的所有普通操作(节点的增删改查),如果整合一个基本操作,都成为splaying,按照一定元素顺序Splaying 这个树,即重新排列了节点,并且这个节点被置为根。一种方法是,第一步,基于标准二叉树的执行对该节点原有的操作,然后基于树的旋转,使得这个节点成为根节点。相应的,一个top-down算法可以整合查询和树的重新组织为一个单一的步骤。
头文件:
#ifndef _SPLAY_TREE_H_ #define _SPLAY_TREE_H_ typedef struct tree_node { struct tree_node * left, * right; int key; int size; /* maintained to be the number of nodes rooted here */ void *data; } splay_tree; splay_tree * splaytree_splay (splay_tree *t, int key); splay_tree * splaytree_insert(splay_tree *t, int key, void *data); splay_tree * splaytree_delete(splay_tree *t, int key); splay_tree * splaytree_size(splay_tree *t); #define splaytree_size(x) (((x)==NULL) ? 0 : ((x)->size)) /* This macro returns the size of a node. Unlike "x->size", */ /* it works even if x=NULL. The test could be avoided by using */ /* a special version of NULL which was a real node with size 0. */ #endif
实现代码:
/* An implementation of top-down splaying with sizes D. Sleator <sleator@cs.cmu.edu>, January 1994. This extends top-down-splay.c to maintain a size field in each node. This is the number of nodes in the subtree rooted there. This makes it possible to efficiently compute the rank of a key. (The rank is the number of nodes to the left of the given key.) It it also possible to quickly find the node of a given rank. Both of these operations are illustrated in the code below. The remainder of this introduction is taken from top-down-splay.c. "Splay trees", or "self-adjusting search trees" are a simple and efficient data structure for storing an ordered set. The data structure consists of a binary tree, with no additional fields. It allows searching, insertion, deletion, deletemin, deletemax, splitting, joining, and many other operations, all with amortized logarithmic performance. Since the trees adapt to the sequence of requests, their performance on real access patterns is typically even better. Splay trees are described in a number of texts and papers [1,2,3,4]. The code here is adapted from simple top-down splay, at the bottom of page 669 of [2]. It can be obtained via anonymous ftp from spade.pc.cs.cmu.edu in directory /usr/sleator/public. The chief modification here is that the splay operation works even if the item being splayed is not in the tree, and even if the tree root of the tree is NULL. So the line: t = splay(i, t); causes it to search for item with key i in the tree rooted at t. If it's there, it is splayed to the root. If it isn't there, then the node put at the root is the last one before NULL that would have been reached in a normal binary search for i. (It's a neighbor of i in the tree.) This allows many other operations to be easily implemented, as shown below. [1] "Data Structures and Their Algorithms", Lewis and Denenberg, Harper Collins, 1991, pp 243-251. [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan, JACM Volume 32, No 3, July 1985, pp 652-686. [3] "Data Structure and Algorithm Analysis", Mark Weiss, Benjamin Cummins, 1992, pp 119-130. [4] "Data Structures, Algorithms, and Performance", Derick Wood, Addison-Wesley, 1993, pp 367-375 */ #include "splaytree.h" #include <stdlib.h> #include <assert.h> #define compare(i,j) ((i)-(j)) /* This is the comparison. */ /* Returns <0 if i<j, =0 if i=j, and >0 if i>j */ #define node_size splaytree_size /* Splay using the key i (which may or may not be in the tree.) * The starting root is t, and the tree used is defined by rat * size fields are maintained */ splay_tree * splaytree_splay (splay_tree *t, int i) { splay_tree N, *l, *r, *y; int comp, l_size, r_size; if (t == NULL) return t; N.left = N.right = NULL; l = r = &N; l_size = r_size = 0; /*查找key,一边查找一边进行旋转操作,通过compare函数,这个在c++中需要重载-号*/ for (;;) { comp = compare(i, t->key); if (comp < 0) { if (t->left == NULL) break; if (compare(i, t->left->key) < 0) {/*如果要查询的值比节点值小,且比左子节点小,LL类型*/ y = t->left; /* rotate right ,LL类型,右旋*/ t->left = y->right; y->right = t; t->size = node_size(t->left) + node_size(t->right) + 1; t = y; if (t->left == NULL) break; } r->left = t; /* link right */ r = t; t = t->left; r_size += 1+node_size(r->right); } else if (comp > 0) { if (t->right == NULL) break; if (compare(i, t->right->key) > 0) { y = t->right; /* rotate left */ t->right = y->left; y->left = t; t->size = node_size(t->left) + node_size(t->right) + 1; t = y; if (t->right == NULL) break; } l->right = t; /* link left */ l = t; t = t->right; l_size += 1+node_size(l->left); } else { break; } } l_size += node_size(t->left); /* Now l_size and r_size are the sizes of */ r_size += node_size(t->right); /* the left and right trees we just built.*/ t->size = l_size + r_size + 1; l->right = r->left = NULL; /* The following two loops correct the size fields of the right path */ /* from the left child of the root and the right path from the left */ /* child of the root. */ for (y = N.right; y != NULL; y = y->right) { y->size = l_size; l_size -= 1+node_size(y->left); } for (y = N.left; y != NULL; y = y->left) { y->size = r_size; r_size -= 1+node_size(y->right); } l->right = t->left; /* assemble */ r->left = t->right; t->left = N.right; t->right = N.left; return t; } splay_tree * splaytree_insert(splay_tree * t, int i, void *data) { /* Insert key i into the tree t, if it is not already there. */ /* Return a pointer to the resulting tree. */ splay_tree * new; if (t != NULL) { t = splaytree_splay(t, i); if (compare(i, t->key)==0) { return t; /* it's already there */ } } new = (splay_tree *) malloc (sizeof (splay_tree)); assert(new); if (t == NULL) { new->left = new->right = NULL; } else if (compare(i, t->key) < 0) { new->left = t->left; new->right = t; t->left = NULL; t->size = 1+node_size(t->right); } else { new->right = t->right; new->left = t; t->right = NULL; t->size = 1+node_size(t->left); } new->key = i; new->data = data; new->size = 1 + node_size(new->left) + node_size(new->right); return new; } splay_tree * splaytree_delete(splay_tree *t, int i) { /* Deletes i from the tree if it's there. */ /* Return a pointer to the resulting tree. */ splay_tree * x; int tsize; if (t==NULL) return NULL; tsize = t->size; t = splaytree_splay(t, i); if (compare(i, t->key) == 0) { /* found it */ if (t->left == NULL) { x = t->right; } else { x = splaytree_splay(t->left, i); x->right = t->right; } free(t); if (x != NULL) { x->size = tsize-1; } return x; } else { return t; /* It wasn't there */ } } #if 0 static splay_tree *find_rank(int r, splay_tree *t) { /* Returns a pointer to the node in the tree with the given rank. */ /* Returns NULL if there is no such node. */ /* Does not change the tree. To guarantee logarithmic behavior, */ /* the node found here should be splayed to the root. */ int lsize; if ((r < 0) || (r >= node_size(t))) return NULL; for (;;) { lsize = node_size(t->left); if (r < lsize) { t = t->left; } else if (r > lsize) { r = r - lsize -1; t = t->right; } else { return t; } } } #endif
splaytree算法复杂度:http://en.wikipedia.org/wiki/Splay_tree
平摊分析情况下:
Tree | ||
1985 | ||
Daniel Dominic Sleator and Robert Endre Tarjan | ||
Average | Worst case | |
O(n) | O(n) | |
O(log n) | amortized O(log n) | |
O(log n) | amortized O(log n) | |
O(log n) | amortized O(log n) |
发表评论
-
41 First Missing Positive——leetcode
2015-04-12 10:52 1001Given an unsorted integer a ... -
146 LRU Cache——leetcode
2015-04-12 09:43 1295146 LRU Cache 这个基 ... -
56 Merge Intervals——leetcode
2015-04-11 20:55 909这个是基于排序库实现的 56 Merge Interv ... -
57 Insert Interval——leetcode
2015-04-11 20:52 167157 Insert Interval /** * ... -
68 Text Justification——leetcode
2015-04-11 20:39 68368 Text Justification clas ... -
188 Best Time to Buy and Sell Stock IV——leetcode
2015-04-11 20:29 898class Solution { public: ... -
200 Number of Islands——leetcode
2015-04-11 20:18 1645这个是图像中的填充技术,即选择一个种子,然后对其周边联通的的 ... -
程序生成组合C(N,K)输出
2015-01-15 00:15 1104本来是想在网上搜索下现成的,结果看到一堆想吐的,尼玛啊,什 ... -
BoxesDiv2——SRM 622 DIV2
2014-05-30 06:30 937import java.util.*; public cl ... -
MixingColors--SRM621 DIV2
2014-05-22 14:27 828Problem Statement for Mixi ... -
梯度下降算法——notes
2014-05-15 22:34 1408Andrew,Ng的学习笔记 在希腊人的<< ... -
Problem A. Part Elf, Round 1C JAM,2014
2014-05-12 11:31 621Problem A. Part Elf This ... -
排序算法时间复杂度,稳定性综合一览表
2014-05-11 08:53 2372原始图片来自于国外某人的博客 写道 http://sin ... -
道路匹配——稀疏数据轨迹点的匹配
2012-12-25 17:05 8231道路匹配分析与设 ... -
Splay Tree
2012-11-27 13:16 311这个是扩展树的C语言实现版本,这个是自上而下且节点带大小(si ...
相关推荐
splay tree C# code 伸展树的C#代码实现 我看到没有C#实现版本,所以就把java代码转化成C#实现了一把
SplayTree详细解释
展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
SplayTree优化版C源代码,带有完整的解释,其实就是置顶向下的Splay tree
快速八叉树 :(非递归)和简单(<1000行代码)实现是直接从Wikipedia改编而成的,使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'
erl-splay-tree:Erlang中的splay-tree实现
伸展树(Splay tree)图解与实现(2020.10.22).pdf
伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
伸展树的主要特点:每次访问某个节点时,都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间,也就是说它的摊还时间为O(F(N))。 伸展数的主要难点:展开函数的实现。 基本操作插入、删除、...
一个简单的 AVL树、splay树、以及二叉搜索树的代码实现 也可在我的github仓库中下载: https://github.com/yunwei37/myClassNotes
节点展开树展开树实现进行中...
Splay,平衡树的一种,支持部分区间操作。
top_down splay_tree 伸展树
红黑树、平衡二叉树、B树、二叉搜索树和SPlay树的C++源码实现,带工程
Splay树是一种自平衡二进制搜索树。 该树不需要存储任何其他信息,这使它的存储效率更高。 在每次调用甚至搜索之后,展开树都会更改其结构,因此,它使您可以更快地找到最近使用的数据。 Splay树不适用于很少或永远...
Algorithm-splay_tree.zip,具有摊销访问权的自平衡二叉树,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。 [1] 在伸展树上...
扩展树是一种自我调整的二进制搜索树,具有最近访问的元素可以快速再次访问的附加属性。 它在O(log n)摊销时间内执行基本操作,例如插入,查找和删除。 -文献资料请参阅。 该文档包括一些示例。安装Cargo.toml...
该程序是播放和音频播放器的简单curses前端。 它更像是在exec和fork中进行的实验。.但是它是有用的,而且轻巧。
游戏树展开树的简单实现。 所有函数都具有与 STL 映射函数类似的调用。细节此实现是出于教育目的。 对该库进行了基本测试。 如果您发现错误,请报告它,我会尝试修复它。特征C++11 组件前向迭代器和 const_iterator ...