存档

作者存档

伸展树的自顶向下伸展(top-down splay)

2011年11月20日 没有评论 4,507 次浏览

假设在当前伸展树中的X节点处进行伸展,X的父亲节点为P(X)(如果X的父亲节点存在),X的祖父节点为G(X)(如果X的祖父节点存在)。 从前面的讲述,我们知道自底向上伸展的方法是在完全查找完之后再进行的伸展操作(如果找到待查节点X,就在节点X处进行伸展操作;如果未找到待查节点X即遇到了空节点,就在最后一个非空节点处进行伸展操作),而自顶向下伸展将在节点查找的过程中就同时进行着伸展操作。 自顶向下伸展操作将伸展树分为三部分: 左树:包含所有已经知道比待查节点X小的节点。 右树:包含所有已经知道比待查节点X大的节点。 中树:包含所有其它节点。 在中树自根向下进行节点查找(每次向下比较两个节点),根据查找情况将中树中的节点移动(此处的移动是指将节点和中树的连接断开,而将节点连接到左或右树的适当位置。)到左树或右树(如有必要则会先对中树进行旋转再进行节点移动)。 初始状态时,左树和右树都为空,而中树为整个原伸展树。随着查找的进行,左树和右树会因节点的逐渐移入变大,中树会因节点的逐渐移出变小。最后查找结束(找到或遇到空节点)时组合左中右树并是伸展树自顶向下伸展方法的最终结果。 下图所给旋转为b的左右子树都存在时,并且图中只画出了待查节点比a小的情况,比a大的情况可由对称关系推出。伸展树的自顶向下伸展示意图: ... [阅读更多]

分类: 数据结构 标签:

伸展树的自底向上伸展实例

2011年11月20日 没有评论 3,505 次浏览

几个图就可以看明白了,伪码一的旋转过程以及结果: 伪码二的旋转过程以及结果: 结论:前述的两种伸展伪码对于同一伸展树在同一节点开始伸展最后得到的伸展树结构不一定完全一致。 ... [阅读更多]

分类: 数据结构 标签:

伸展树的自底向上伸展(bottom-up splay)

2011年11月20日 没有评论 3,073 次浏览

假设在当前伸展树中的X节点处进行伸展,X的父亲节点为P(X)(如果X的父亲节点存在),X的祖父节点为G(X)(如果X的祖父节点存在)。伸展树的自底向上伸展伪码为: FUNC bottom-up-splay DO IF... [阅读更多]

分类: 数据结构 标签:

伸展树介绍

2011年11月20日 没有评论 3,263 次浏览

假想这么一种情况,我们想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更短,那些查频率比较高的节点就应该经常处于比较靠近树根的位置,于是最直观的想法就是将每次查找访问的节点都放到树根处,这样再次查找该节点时将会很快的找到该节点。在每次查找访问节点之后对该树进行重构,将被查找的节点搬移到树根,这种自调整型式的二叉查找树就是splay... [阅读更多]

分类: 数据结构 标签:

Kernel Mode Linux

2011年11月17日 没有评论 6,393 次浏览

User Mode Linux肯定很多人都知道,是一个让Linux二进制镜像可以运行到应用层的内核补丁,目前该补丁已经合入到Kernel Mainline。 UML不是这篇日志的主角,我们要介绍的KML(Kernel Mode... [阅读更多]

dlmalloc解析连载完整word文档

2011年11月15日 6 条评论 9,995 次浏览

把cu个人博客的这篇文章转载过来,呵呵。 目 录 1. 本文档介绍 2.边界标记法 3. 分箱式内存管理 4. 核心结构体malloc_state 5. 内存分配相关函数 5.1 函数dlmalloc 5.2 函数tmalloc_small 5.3... [阅读更多]

我的孤独,没人能懂。

2011年11月15日 3 条评论 4,057 次浏览

很想写点什么,就如同有烟瘾的人几天不抽烟就会焦躁不安一样,当然,我不抽烟,我只是想写点文字,作为已攀登在文学青年与文艺青年之颠的2B青年——我,这是完全可以理解的。 这也不能完全怪我,只能说最近几天一直在看几个同等人类的博客,他人悲春伤秋,勾起了我的忧愁。我太恋旧,总觉得遗憾,却又无能为力,所以有时候想想,喜新厌旧未必就是坏事,至少不会沉溺于过去。 对于人生,我本就没有什么奢望,更别谈什么理想,甚至一直不知道为什么而活着,却也就这样活着。我本想落尽那三千烦恼丝,碎了那三生石,入了那不二法门,却又不畏畏缩缩而不曾实言。到底还是留恋酒绿灯红情欲人间?! 岁月悠悠难回首,艳香迷醉心已染。孤独衍生的黑暗,可曾还有丝丝值得期待的光亮?明天,我会在哪里? ... [阅读更多]

分类: 生活点滴 标签: ,

中秋节

2011年9月13日 3 条评论 6,453 次浏览

中秋节,部门同事一起在中山公园happy,玩得很开心,也吃撑了,O(∩_∩)O~。 贴图三张,留作纪念。 中山公园: 中秋之月: 三盏孔明灯: ... [阅读更多]

分类: 生活点滴 标签: