王朝百科
分享
 
 
 

平衡树

王朝百科·作者佚名  2010-05-15  
宽屏版  字体: |||超大  

动机

对一棵 search tree 进行查询/新增/删除 等动作, 所花的时间与树的高度 h 成比例, 并不与树的容量 n 成比例。 如果可以让树维持矮矮胖胖的好身材, 也就是让 h 维持在 O(lg n), 上述工作就很省时间。 能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做 balanced search tree 平衡树。

旋转 -- 不破坏左小右大特性的小手术

平衡树有很多种, 其中有几类树维持平衡的方法, 都是靠整形小手术:

y x

/ /

x C <==> A y

/ /

A B B C

图中 x 与 y 为 nodes; A, B, C 为一整串的 subtrees。 试想: 如果 x 原来是 y 的 left child; 现在想将 x 变成 parent, 则树的其它部分应如何变化? y 必须变成 right child, 这样才能维持 BST 的特性 -- 左小右大。 至于 x 与 y 以下的其它部分, 可以整串 subtree 一起处理: x 原来的 left subtree (A), 调整后还是 x 的 left subtree; y 原来的 right subtree (C), 调整后还是 y 的 right subtree; 而 x 原来的 right subtree (B), 调整后很自然只有一个地方可以放: 变成 y 的 left subtree。 这些规则都不需要记, 因为如果你希望调整后还维持 BST 左小右大的特性, 这是唯一的答案。 把 x,y 两个值及 A,B,C 三棵 subtrees 内的三串值画在数在线看更清楚:

--------- x --------- y ---------

A B C

这个动作, 称为 right rotation 向右旋转, 或称为顺时针旋转 (clockwise)。 原来的 parent (y) 叫做 pivot, 原来的 child (x) 叫做 rotator。

把上图反过来看, 如果原来的树长得像右图, 想将它改成左图, 则称为 left rotation 向左旋转, 或称为逆时针旋转 (counter-clockwise)。 原来的 parent (x) 叫做 pivot, 原来的 child (y) 叫做 rotator。

数一下旧的 parent 左 subtree 有多少 ndoes? 右 subtree 有多少 nodes? 旋转后新的 parent 左右 subtrees 又各有多少 nodes? 发现右旋的效果会让树的重心往右移; 而左旋的效果则是让树的重心往左移。 如果你的树经历过许多 insert/remove 等等岁月的沧桑, 越长越歪, 在适当的时候对它进行一下旋转手术, 不就可以将它变回矮矮胖胖四平八稳的美丽模样吗? 所以左旋与右旋是几种平衡树共同采用的基本手术; 只不过不同的平衡树, 选择不同的时机/条件来动手术而已。

左子节点与右子节点对称的树就是平衡树,否则就是非平衡树。

非平衡树会影响树中数据的查询,插入和删除的效率。比如当一个二叉树极不平衡时,即所有的节点都在根的同一侧,此时树没有分支,就变成了一个链表。数据的排列是一维的,而不是二维的。在这种情况下,查找的速度下降到O(N),而不是平衡二叉树的O(logN)。

为了能以较快的时间O(logN)来搜索一棵树,需要保证树总是平衡的(或者至少大部分是平衡的)。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。

几种主要的二叉平衡树:

红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项,插入程序要检查不会破坏树一定的特征。如果破坏了,程序就会进行纠正,根据需要更改树的结构。通过维持树的特征,保持了树的平衡。

红黑树有两个特征:

(1) 节点都有颜色

(2) 在插入和删除过程中,要遵循保持这些颜色的不同排列的规则。

红黑规则:

1. 每一个节点不是红色的就是黑色的

2. 根总是黑色的

3. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定成立)

4. 从根到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点。

(空子节点是指非叶节点可以接子节点的位置。换句话说,就是一个有右子节点的节点可能接左子节点的位置,或是有左子节点的节点可能接右子节点的位置)

AVL树,它或者是一颗空二叉树,或者是具有下列性质的二叉树:

(1) 其根的左右子树高度之差的绝对值不能超过1;

(2) 其根的左右子树都是二叉平衡树。

AVL树查找的时间复杂度为O(logN),因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树,依次向下查找插入点,依次向上平衡树,AVL树不如红黑树效率高,也不如红黑树常用。

AVL树插入的C++代码:

template <class T>

ResultCode AVLTree<T>::Insert(AVLNode<T> * &p,T &x,bool &unBalanced)

...{

ResultCode result=Success;

if(p==null)...{//插入新节点

p=new AVLNode<T>(x);

unBalanced=true;

}else if(x<p->element)...{//新节点插入左子树

result=Insert(p->lChild,x,unBalanced);

if(unBanlanced)...{

switch(p->bF)...{

case -1:

p->bF=0;

unBalanced=false;

break;

case 0:

p->bF=1;

break;

case 1:

LRotation(p,unBalanced);

}

}

}else if(x==p->element)...{//有重复元素,插入失败

unBalanced=false;

x=p->element;

result=Duplicate;

}else...{//新节点插入右子树

result=Insert(p->rChild,x,unBalanced);

if(unBalanced)...{

switch(p->bF)...{

case 1:

p->bF=0;

unBalanced=false;

break;

case 0:

p->bF=-1;

break;

case -1:

RRotation(p,unBalanced);

}

}

}

return result;

}

template <class T>

void AVLTree<T>::LRotation(AVLNode<T> * &s,bool &unBalanced)

...{

AVLNode<T> *u,*r=s->lChild;

if(r->bF==1)...{//LL旋转

s->lChild=r->rChild;

r->rChild=s;

s->bF=0;

s=r; //s指示新子树的根

}else...{ //LR旋转

u=r->rChild;

r->rChild=u->lChild;

u->lChild=r;

s->lChild=u->rChild;

u->rChild=s;

switch(u->bF)...{

case 1:

s->bF=-1;

r->bF=0;

break;

case 0:

s->bF=r->bF=0;

break;

case -1:

s->bF=0;

r->bF=1;

}

s=u; //s指示新子树的根

}

s->bF=0; //s的平衡因子为0

unBalanced=false; //结束重新平衡操作

}

通常我们使用二叉树的原因是它可以用O(logn)的复杂度来查找一个数,删除一个数,对吧??可是有时候会发现树会退化,这个就可能使O(logn)->O(n)的了,那么还不如用直接搜一次呢!!所以我们就要想办法使一棵树平衡。而我仅仅看了(AVL)的那个,所以也仅仅能说(AVL)的那个,至于(TREAP),我还不懂,如果你们知道算法的话,欢迎告诉我~!谢谢~

首先引入一个变量,叫做平衡因子(r),节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡,就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0,-1,1.

其次,我要介绍旋转,旋转有两种方式,就是左旋(顺时针旋转)和右旋(逆时针旋转)。

左旋(左儿子代替根):即用左儿子取代根,假设我们要旋转以X为根,LR分别为X的左右儿子,那么我们只需要把L的右儿子取代X的左儿子,然后把更新后的X赋值为L的右儿子,就可以了。

右旋(右儿子代替根):即用右儿子取代根,假设我们要旋转以X为根,LR分别为X的左右儿子,那么我们只需要把R的左儿子取代X的右儿子,然后把更新后的X赋值为L的左儿子,就可以了。

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
如何用java替换看不见的字符比如零宽空格&#8203;十六进制U+200B
 干货   2023-09-10
网页字号不能单数吗,网页字体大小为什么一般都是偶数
 干货   2023-09-06
java.lang.ArrayIndexOutOfBoundsException: 4096
 干货   2023-09-06
Noto Sans CJK SC字体下载地址
 干货   2023-08-30
window.navigator和navigator的区别是什么?
 干货   2023-08-23
js获取referer、useragent、浏览器语言
 干货   2023-08-23
oscache遇到404时会不会缓存?
 干货   2023-08-23
linux下用rm -rf *删除大量文件太慢怎么解决?
 干货   2023-08-08
刀郎新歌破世界纪录!
 娱乐   2023-08-01
js实现放大缩小页面
 干货   2023-07-31
生成式人工智能服务管理暂行办法
 百态   2023-07-31
英语学习:过去完成时The Past Perfect Tense举例说明
 干货   2023-07-31
Mysql常用sql命令语句整理
 干货   2023-07-30
科学家复活了46000年前的虫子
 探索   2023-07-29
英语学习:过去进行时The Past Continuous Tense举例说明
 干货   2023-07-28
meta name="applicable-device"告知页面适合哪种终端设备:PC端、移动端还是自适应
 干货   2023-07-28
只用css如何实现打字机特效?
 百态   2023-07-15
css怎么实现上下滚动
 干货   2023-06-28
canvas怎么画一个三角形?
 干货   2023-06-28
canvas怎么画一个椭圆形?
 干货   2023-06-28
canvas怎么画一个圆形?
 干货   2023-06-28
canvas怎么画一个正方形?
 干货   2023-06-28
中国河南省郑州市金水区蜘蛛爬虫ip大全
 干货   2023-06-22
javascript简易动态时间代码
 干货   2023-06-20
感谢员工的付出和激励的话怎么说?
 干货   2023-06-18
 
>>返回首页<<
 
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有