设为首页 加入收藏

TOP

数据结构之 伸展树个人笔记
2018-11-02 12:08:19 】 浏览:58
Tags:数据结构 伸展 个人 笔记

阅读了skywang的伸展树的讲解,觉得讲的很不错,再次也推荐大家无论是新手还是老手都可以去阅读下。

-----------------------------------------------------------------------------------------

概要

本章介绍伸展树。它和"二叉查找树"和"AVL树"一样,都是特殊的二叉树。在了解了"二叉查找树"和"AVL树"之后,学习伸展树是一件相当容易的事情。和以往一样,本文会先对伸展树的理论知识进行简单介绍,然后给出C语言的实现。后序再分别给出C++和Java版本的实现;这3种实现方式的原理都一样,选择其中之一进行了解即可。若文章有错误或不足的地方,希望您能不吝指出!

目录
1. 伸展树的介绍
2. 伸展树的C实现
3. 伸展树的C测试程序

转载请注明出处:http://www.cnblogs.com/skywang12345/p/3604238.html

---------------------------------------------------------------------------------------------

特性要点:

1.如果寻找的key值小于tree->key值的话,则进行右旋:

 1 Node N, *l, *r, *c;
 2 
 3 N.left = N.right = NULL;
 4 l = r = &N;
 5 if(key < tree->key)
 6 {
 7   if(key< tree->left->key)
 8   {
 9            c = tree -> left;
10            tree->left = c->right;
11            c->right = tree;
12            tree = c;        
13   }
14       r->left = tree;                               /* 02, link right */
15       r = tree;
16       tree = tree->left;      
17 }          

2.寻找的key值大于tree->key的话,则左旋,同理之;

3.如何简单的判断左旋还是右旋:

  因为伸展树就是为了将寻找的key值对应的节点变为根节点,所以根据二叉树的特性:x节点包含关键字key,如果y是x的左子树的一个节点,则 key[y]<= key[x]。如果y是x的右子树的一个节点,则key[y] >= key[x]。那么如果key > tree->key ,则key就在tree的右子树的某个节点上,那么你就需要将右子树旋转直到根节点上。那么根据生活常识,你需要向左旋转才能将右子树旋转到根节点上。右旋同理之。

而所谓的左旋、右旋,则相当于;

左旋:将节点旋转为右孩子的左节点

右旋:将节点旋转为左孩子的右节点

 

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇学习UDP 下一篇Keil开发环境如何生成BIN文件

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }