姜异康父亲,维尼夫妇婚纱照图片,细胞器系统内的分工合作
本章介绍伸展树。它和""和""一样,都是特殊的二叉树。在了解了""和""之后,学习伸展树是一件相当容易的事情。和以往一样,本文会先对伸展树的理论知识进行简单介绍,然后给出c语言的实现。后序再分别给出c++和java版本的实现;这3种实现方式的原理都一样,选择其中之一进行了解即可。若文章有错误或不足的地方,希望您能不吝指出!
目录
1.
2.
3.
转载请注明出处:
---------------------------------------------------------------------------------------------
特性要点:
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的右子树的某个节点上,那么你就需要将右子树旋转直到根节点上。那么根据生活常识,你需要向左旋转才能将右子树旋转到根节点上。右旋同理之。
而所谓的左旋、右旋,则相当于;
左旋:将节点旋转为右孩子的左节点
右旋:将节点旋转为左孩子的右节点
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论