- 浏览: 48321 次
- 性别:
- 来自: 北京
文章分类
最新评论
转载http://hxraid.iteye.com/blog/609949
在上一个专题中,我们在谈论二叉查找树的效率的时候。不同结构的二叉查找树,查找效率有很大的不同(单支树结构的查找效率退化成了顺序查找)。如何解决这个问题呢?关键在于如何最大限度的减小树的深度。正是基于这个想法,平衡二叉树出现了。
平衡二叉树的定义 (AVL—— 发明者为Adel'son-Vel'skii 和 Landis)
平衡二叉查找树,又称 AVL树。 它除了具备二叉查找树的基本特征之外,还具有一个非常重要的特点:它 的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1。 也就是说AVL树每个节点的平衡因子只可能是-1、0和1(左子树高度减去右子树高度)。
那么如何是二叉查找树在添加数据的同时保持平衡呢?基本思想就是:当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若 破坏,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达 到新的平衡。所谓最小不平衡子树 指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
平衡二叉树的操作
1. 查找操作
平衡二叉树的查找基本与二叉查找树相同。
2. 插入操作
在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是: 旋转 。 下面我们归纳一下平衡旋转的4中情况
1) 绕某元素左旋转
80 90
/ \ 左旋 / \
60 90 ---- -> 80 120
/ \ / \ /
85 120 60 85 100
/
100
a) BST树 b ) AVL树
分析一下:在插入数据100之前,a图的B ST树只有80节点的平衡因子是-1(左高-右高),但整棵树还是平衡的。加入100之后,80节点的平衡因子就成为了-2,此时平衡被破坏。需要左旋转成b 图。
当树中节点X的右孩子的右孩子上插入新元素,且平衡因子从-1变成-2后,就需要绕节点X进行左旋转。
2) 绕某元素右旋转
100 85
/ \ 右旋 / \
85 120 ------ -> 60 100
/ \ \ / \
60 90 80 90 120
\
80
a) B ST树 b) AVL树
当树中节点X的左孩子的左孩子上插入新元素,且平衡因子从1变成2后,就需要绕节点X进行右旋转。
3) 绕某元素的左子节点左旋转,接着再绕该元素自己右旋转。 此情况下就是左旋与右旋 的结合,具体操作时可以分 解成这两种操作,只是围绕点不一样而已。
100 100 90
/ \ 左旋 / \ 右旋 / \
80 120 ------> 90 120 ------> 80 100
/ \ / / \ \
60 90 80 60 85 120
/ / \
85 60 85
当树中节点X的左孩子的右孩子上插入新元素,且 平衡因子从1变成2后,就需要 先绕X的左子节点Y左旋转,接着再绕X右旋转
4) 绕某元素的右子节点右旋转,接着再绕该元素自己左旋转。 此情况下就是 右旋与左旋 的结合,具体操作时可以分解 成这两种操作,只是围绕点不一样而已 。
80 80 85
/ \ 右 旋 / \ 左 旋 / \
60 100 ------> 60 85 -------> 80 100
/ \ \ / / \
85 120 100 60 90 120
\ / \
90 90 120
当树中节点X的右孩子的左孩子上插入新元素,且 平衡因子从-1变成-2后,就需要 先绕X的右子节点Y右旋转,接着再绕X左旋转
平衡二叉树性能分析
平衡二叉树的性能优势:
很显然,平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。
平衡二叉树的缺陷:
(1) 很遗憾的是,为了保证高度平衡,动态插入和删除的代价也随之增加。因此,我们在下一专题中讲讲《红黑树》 这种更加高效的查找结构。
(2) 所有二叉查找树结构的查找代价都与树高是紧密相关的,能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点,在后面专题中我们将通过《多路查找树/B-树/B+树 》来介绍。
(3) 在大数据量查找环境下(比如说系统磁盘里的文件目录,数据库中的记录查询 等),所有的二叉查找树结构(BST、AVL、RBT)都不合适。如此大规模的数据量(几G数据),全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧。问题就来了:假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。大家都知道,硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。 查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下,平衡二叉树的效率就很成问题了。对这一问题的解决:我们也会在《多路查找树/B-树/B+树 》将详细分析。
上面提到的红黑树和多路查找树都是属于深度有界查找树(depth-bounded tree —DBT)
平衡二叉树的插入操作代码(平衡旋转)
- package net.hr.algorithm.search;
- /**平衡因子枚举类*/
- enum B
- alanceFactor{
- LH("左子树高"),EH("左右等高"),RH("右子树高");
- private String illustration="";
- private BalanceFactor(String s){
- this.illustration=s;
- }
- public String toString(){
- return this.illustration;
- }
- }
- /**
- * 平衡二叉树结点
- */
- class AVLNode<E extends Comparable<E>>{
- /**结点关键字*/
- E key=null;
- /**结点的平衡因子*/
- BalanceFactor bFactor=BalanceFactor.EH;
- /**结点的直接父亲*/
- AVLNode<E> parent=null;
- /**结点的左右孩子*/
- AVLNode<E> lchild,rchild=null;
- AVLNode(E k){
- this.key=k;
- }
- /**
- * 格式输出结点
- */
- public String toString(){
- //String fomateStr="";
- //if(this.lchild==null)
- String lchildStr=(this.lchild==null)?"null":this.lchild.key.toString();
- String rchildStr=(this.rchild==null)?"null":this.rchild.key.toString();
- return this.key+"[lchild="+lchildStr+",rchild="+rchildStr+"]";
- }
- }
- /**
- * 平衡二叉查找树
- * @author heartraid
- */
- public class AVL<E extends Comparable<E>> {
- /**树根*/
- private AVLNode<E> root=null;
- /**当前树是否变高*/
- public boolean isTaller=false;
- public AVL(){
- }
- public boolean insert(E key){
- System.out.print("插入["+key+"]:");
- if(key==null) return false;
- if(root==null){
- System.out.println("插入到树根。");
- root=new AVLNode<E>(key);
- return true;
- }
- else{
- System.out.print("搜索路径[");
- return insertAVL(key,root);
- }
- }
- private boolean insertAVL(E key,AVLNode<E> node){
- System.out.print(node.key+" —>");
- // 树中存在相同的key,不需要插入
- if(node.key.compareTo(key)==0){
- System.out.println("]. 搜索有相同关键字,插入失败");
- isTaller=false;
- return false;
- }
- else{
- //左子树搜索
- if(node.key.compareTo(key)>0){
- //当前node的左孩子为空,则插入到结点的做孩子并修改结点的平衡因子为LH
- if(node.lchild==null){
- System.out.println("]. 插入到"+node.key+"的左孩子");
- AVLNode<E> newNode=new AVLNode<E>(key);
- node.lchild=newNode; //设置左孩子结点
- newNode.parent=node; //设置父亲结点
- isTaller=true; //树长高了
- }
- //左孩子不为空,则继续搜索下去
- else{
- insertAVL(key,node.lchild);
- }
- //当前如果树长高了,说明是因为左孩子的添加改变了平衡因子(左高)。
- if(isTaller){
- System.out.print(" 树变化了,"+node.key+"的平衡因子变化");
- switch(node.bFactor){
- //原来结点平衡因子是LH(bf=1),则左高以后bf=2,因此需要做左平衡旋转
- case LH: {
- System.out.println("[LH=1 ——> LH=2]. 出现了不平衡现象[左比右高2]");
- System.out.println(" ★ 以"+node.key+"为根将树进行左平衡处理");
- leftBalance(node);
- isTaller=false;
- break;
- }
- //原来结点平衡因子是EH(bf=0),则左高了以后bf=1,不需要平衡处理。
- case EH:{
- System.out.println("[EH=0 ——> LH=1]. 没有不平衡现象");
- node.bFactor=BalanceFactor.LH;
- isTaller=true;
- break;
- }
- //原来结点平衡因子是RH(bf=-1),则左高以后bf=0,不需要平衡处理。
- case RH:{
- System.out.println("[RH=-1 ——> EH=0]. 没有不平衡现象");
- node.bFactor=BalanceFactor.EH;
- isTaller=false;
- break;
- }
- }//end switch
- }//end if
- }//end if
- //右子树搜索
- else{
- if(node.rchild==null){
- System.out.println("]. 插入到"+node.key+"的右孩子");
- AVLNode<E> newNode=new AVLNode<E>(key);
- node.rchild=newNode; //设置右孩子结点
- newNode.parent=node; //设置父亲结点
- isTaller=true; //树长高了
- }
- else{
- insertAVL(key,node.rchild);
- }
- //当前如果树长高了,说明是因为右孩子的添加改变了平衡因子(右高)。
- if(isTaller){
- System.out.print(" 树变化了,"+node.key+"的平衡因子变化");
- switch(node.bFactor){
- //原来结点平衡因子是LH(bf=1),则右高以后bf=0,不需要平衡处理。
- case LH: {
- System.out.println("[LH=1 ——> EH=0]. 没有不平衡现象");
- node.bFactor=BalanceFactor.EH;
- isTaller=false;
- break;
- }
- //原来结点平衡因子是EH(bf=0),则右高了以后bf=-1,不需要平衡处理。
- case EH:{
- System.out.println("[EH=0 ——> RH=-1]. 没有不平衡现象");
- node.bFactor=BalanceFactor.RH;
- isTaller=true;
- break;
- }
- //原来结点平衡因子是RH(bf=-1),则右高以后bf=0,因此需要做右平衡旋转。
- case RH:{
- System.out.println("[RH=-1 ——> RH=-2]. 出现了不平衡现象[左比右矮2]");
- rightBalance(node);
- isTaller=false;
- break;
- }
- }//end switch
- }//end if(isTaller)
- }//end else
- return true;
- }//end else
- }
- /**
- * 左平衡旋转处理
- * 先对node的左子树进行单左旋处理,在对node树进行单右旋处理
- *
- * 100 100 90
- * / \ 左旋 / \ 右旋 / \
- * 80 120 ------> 90 120 ------> 80 100
- * / \ / / \ \
- * 60 90 80 60 85 120
- * / / \
- * 85 60 85
- *
- * @param node 需要做处理的子树的根结点
- */
- private void leftBalance(AVLNode<E> node){
- // node.parent指向新的孩子结点
- AVLNode<E> lc=node.lchild;//lc指向node的左孩子结点
- switch(lc.bFactor){
- case LH:{ //新结点插入在node的左孩子的左子树上,则需要单右旋处理
- System.out.println(" ┖ 对"+node.key+"进行单右旋转处理");
- node.bFactor=lc.bFactor=BalanceFactor.EH;
- rRotate(node);
- break;
- }
- case RH:{ //新结点插入在node的左孩子的右子树上,需要双旋处理
- System.out.println(" ┖ 对"+node.key+"的左子树进行单左旋转处理,再对其本身树进行单右循环处理");
- AVLNode<E> rd=lc.rchild; //rd指向node左孩子的右子树根
- switch(rd.bFactor){ //修改node与其左孩子的平衡因子
- case LH:{
- node.bFactor=BalanceFactor.RH;
- lc.bFactor=BalanceFactor.EH;
- break;
- }
- case EH:{
- node.bFactor=lc.bFactor=BalanceFactor.EH;
- break;
- }
- case RH:{
- node.bFactor=BalanceFactor.EH;
- lc.bFactor=BalanceFactor.LH;
- break;
- }
- }//switch
- rd.bFactor=BalanceFactor.EH;
- lRotate(node.lchild);
- rRotate(node);
- break;
- }
- }
- }
- /**
- * 右平衡旋转处理
- *
- * 80 80 85
- * / \ 右 旋 / \ 左 旋 / \
- * 60 100 ------> 60 85 -------> 80 100
- * / \ \ / / \
- * 85 120 100 60 90 120
- * \ / \
- * 90 90 120
- *
- * @param node
- */
- private void rightBalance(AVLNode<E> node){
- AVLNode<E> lc=node.rchild;//lc指向node的右孩子结点
- switch(lc.bFactor){
- case RH:{ //新结点插入在node的右孩子的右子树上,则需要单左旋处理
- node.bFactor=lc.bFactor=BalanceFactor.EH;
- lRotate(node);
- break;
- }
- case LH:{ //新结点插入在node的右孩子的左子树上,需要双旋处理
- AVLNode<E> rd=lc.lchild; //rd指向node右孩子的左子树根
- switch(rd.bFactor){ //修改node与其右孩子的平衡因子
- case LH:{
- node.bFactor=BalanceFactor.EH;
- lc.bFactor=BalanceFactor.RH;
- break;
- }
- case EH:{
- node.bFactor=lc.bFactor=BalanceFactor.EH;
- break;
- }
- case RH:{
- node.bFactor=BalanceFactor.LH;
- lc.bFactor=BalanceFactor.EH;
- break;
- }
- }//switch
- rd.bFactor=BalanceFactor.EH;
- rRotate(node.rchild);
- lRotate(node);
- break;
- }
- }
- }
- /**
- * 对以node为根的子树进行单右旋处理,处理后node.parent指向新的树根,即旋转之前
- * node的左孩子结点
- * 100<-node.parent 80<-node.parent
- * / / \
- * 80 ———> 60 100
- * / \ /
- * 60 85 85
- */
- private void rRotate(AVLNode<E> node){
- AVLNode<E> lc=node.lchild;//lc指向node的左孩子结点
- node.lchild=lc.rchild;
- lc.rchild=node;
- if(node.parent==null){
- root=lc;
- }
- else if(node.parent.lchild.key.compareTo(node.key)==0)
- node.parent.lchild=lc;
- else node.parent.rchild=lc;
- }
- /**
- * 对以node为根的子树进行单左旋处理,处理后node.parent指向新的树根,即旋转之前
- * node的右孩子结点
- * 100<-node.parent 110<-node.parent
- * \ / \
- * 110 ————> 100 120
- * / \ \
- * 105 120 105
- */
- private void lRotate(AVLNode<E> node){
- AVLNode<E> rc=node.rchild;//lc指向node的右孩子结点
- node.rchild=rc.lchild;
- rc.lchild=node;
- if(node.parent==null){
- root=rc;
- }
- else if(node.parent.lchild.key.compareTo(node.key)==0)
- node.parent.lchild=rc;
- else node.parent.rchild=rc;
- }
- /**
- * 得到BST根节点
- * @return BST根节点f
- */
- public AVLNode<E> getRoot(){
-
return this.root; <
发表评论
-
红黑树【RBT】
2010-10-03 16:20 892转载http://hxraid.iteye.com/b ... -
二叉树【BST】
2010-10-03 16:14 887转载http://hxraid.iteye.com/blog/ ... -
静态查找结构综述
2010-10-03 16:12 764转载http://hxraid.iteye.com/b ... -
根据上排的数填写下排的数
2010-09-13 18:58 1208根据上排给出十个数,在其下排填出对应的十个数, 要求下排每个数 ... -
一个正方形5等分
2010-09-12 16:33 1025每次都二分绝对不能分出奇数个块。以下两张图就是解法,第一张都是 ... -
一个数组的所有的排列
2010-09-04 18:15 829题目:给一个数组,打印出所有的排列 import java. ... -
求1+2+…+n
2010-09-04 17:37 773求1+2+…+n,要求不能使用乘除法、for、while、if ...
相关推荐
C#,自平衡二叉查找树(AVL Tree)的算法与源代码 自平衡二叉查找树(AVL Tree)中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL...
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
平衡二叉查找树代码 AVL 二叉树 查找树
GNU的自平衡叉查找树的源代码库,包括AVL teee和红黑树 redblack tree、二叉查找树。还有PDF的原理说明及HTML的源代码函数解释。
avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...
在根指针T所指的平衡二叉排序树中递归的查找其元素值等于e的数据元素, 若查找成功,则指针p指向该数据元素结点,并返回TRUE,否则指针p 指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲, 其初始...
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是。增加和删除可能需要通过一...
AVL树(平衡二叉查找树) 具有二叉查找树的全部特性。 每个节点的左子树的高度和右子树高度差值小于等于1(平衡二叉树的性质) 左旋:逆时针旋转两个节点,原先的右节点成为新的父节点,原先的父节点成为原先的右...
c代码-平衡二叉查找树 --AVL树
实现了二叉查找树的查找、插入...实现了平衡二叉树(AVL树)的查找、插入、删除和迭代遍历的完整功能,插入时的各种旋转操作按照经典数据结构教材实现,并有详细的注释和说明。删除操作和相关旋转方法有单独描述文档。
平衡二叉排序树的在平衡因子绝对值等于2时开始调整到绝对值为1或0,在平衡因子绝对值为2时,二叉排序树会出现四种不同的情况的树形,因此这时需要分别单独讨论来降低平衡因子。 1.2.7 平衡二叉树的调整方法 平衡...
常见的二叉搜索树的实现代码,包括平衡二叉排序树,红黑树等
平衡二叉树(Balanced Binary Tree)又被称为AVL树。具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的: 二叉排序树的实现...
有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树(Left),导致根节点的平衡因子由1变为2 (2)RR:插入一个新节点到根节点的右子树(Right
二叉排序树查找,Python3 数据结构与算法的... 查找算法: 顺序查找、二分查找、哈希表查找、二叉查找树、平衡二叉查找树(AVL树、红黑树)、平衡多路查找树(B树、B+树);4. LeetCode 和《剑指Offer》刷题、多种方法的题解
平衡二叉树 平衡二叉树(Balanced ...AVL是最先发明的自平衡二叉查找树算法,在AVL中任何节点的两个儿子子树的高度最大差别为一,所以它也被称为高度平衡树。 查找、插入和删除在平均和最坏情况下都是O(log n)。
单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序等共四个实验的实现过程。
AVL Tree source code