`

平衡二叉查找树【AVL】

阅读更多

转载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)


平衡二叉树的插入操作代码(平衡旋转)

Java代码 复制代码
  1. package net.hr.algorithm.search;   
  2. /**平衡因子枚举类*/  
  3. enum B   
  4. alanceFactor{   
  5.     LH("左子树高"),EH("左右等高"),RH("右子树高");   
  6.        
  7.     private String illustration="";   
  8.        
  9.     private BalanceFactor(String s){   
  10.         this.illustration=s;   
  11.     }   
  12.        
  13.     public String toString(){   
  14.         return this.illustration;   
  15.     }   
  16. }   
  17. /**  
  18.  * 平衡二叉树结点  
  19.  */  
  20. class AVLNode<E extends Comparable<E>>{   
  21.     /**结点关键字*/  
  22.     E key=null;   
  23.     /**结点的平衡因子*/  
  24.     BalanceFactor bFactor=BalanceFactor.EH;   
  25.     /**结点的直接父亲*/  
  26.     AVLNode<E> parent=null;   
  27.     /**结点的左右孩子*/  
  28.     AVLNode<E> lchild,rchild=null;   
  29.        
  30.     AVLNode(E k){   
  31.         this.key=k;   
  32.     }   
  33.     /**  
  34.      * 格式输出结点  
  35.      */  
  36.     public String toString(){   
  37.         //String fomateStr="";   
  38.         //if(this.lchild==null)   
  39.         String lchildStr=(this.lchild==null)?"null":this.lchild.key.toString();   
  40.         String rchildStr=(this.rchild==null)?"null":this.rchild.key.toString();   
  41.         return this.key+"[lchild="+lchildStr+",rchild="+rchildStr+"]";   
  42.     }   
  43.   
  44. }   
  45. /**  
  46.  * 平衡二叉查找树  
  47.  * @author heartraid  
  48.  */  
  49. public class AVL<E extends Comparable<E>> {   
  50.   
  51.     /**树根*/  
  52.     private AVLNode<E> root=null;   
  53.     /**当前树是否变高*/  
  54.     public boolean isTaller=false;   
  55.        
  56.     public AVL(){   
  57.     }   
  58.        
  59.        
  60.     public boolean insert(E key){   
  61.         System.out.print("插入["+key+"]:");   
  62.         if(key==nullreturn false;   
  63.         if(root==null){   
  64.             System.out.println("插入到树根。");   
  65.             root=new AVLNode<E>(key);   
  66.             return true;   
  67.         }   
  68.         else{   
  69.             System.out.print("搜索路径[");   
  70.             return insertAVL(key,root);   
  71.         }   
  72.     }   
  73.        
  74.     private boolean insertAVL(E key,AVLNode<E> node){   
  75.         System.out.print(node.key+" —>");   
  76.         // 树中存在相同的key,不需要插入   
  77.         if(node.key.compareTo(key)==0){   
  78.             System.out.println("].  搜索有相同关键字,插入失败");   
  79.             isTaller=false;   
  80.             return false;   
  81.         }   
  82.         else{   
  83.             //左子树搜索   
  84.             if(node.key.compareTo(key)>0){   
  85.                 //当前node的左孩子为空,则插入到结点的做孩子并修改结点的平衡因子为LH   
  86.                 if(node.lchild==null){   
  87.                     System.out.println("].  插入到"+node.key+"的左孩子");   
  88.                     AVLNode<E> newNode=new AVLNode<E>(key);   
  89.                     node.lchild=newNode; //设置左孩子结点   
  90.                     newNode.parent=node; //设置父亲结点   
  91.                     isTaller=true//树长高了   
  92.                 }   
  93.                 //左孩子不为空,则继续搜索下去   
  94.                 else{   
  95.                     insertAVL(key,node.lchild);   
  96.                 }   
  97.                 //当前如果树长高了,说明是因为左孩子的添加改变了平衡因子(左高)。   
  98.                 if(isTaller){   
  99.                     System.out.print("          树变化了,"+node.key+"的平衡因子变化");   
  100.                     switch(node.bFactor){   
  101.                         //原来结点平衡因子是LH(bf=1),则左高以后bf=2,因此需要做左平衡旋转   
  102.                         case LH: {   
  103.                             System.out.println("[LH=1 ——> LH=2]. 出现了不平衡现象[左比右高2]");   
  104.                             System.out.println("          ★ 以"+node.key+"为根将树进行左平衡处理");   
  105.                             leftBalance(node);   
  106.                             isTaller=false;    
  107.                             break;   
  108.                         }   
  109.                         //原来结点平衡因子是EH(bf=0),则左高了以后bf=1,不需要平衡处理。   
  110.                         case EH:{   
  111.                             System.out.println("[EH=0 ——> LH=1]. 没有不平衡现象");   
  112.                             node.bFactor=BalanceFactor.LH;   
  113.                             isTaller=true;   
  114.                             break;   
  115.                         }   
  116.                         //原来结点平衡因子是RH(bf=-1),则左高以后bf=0,不需要平衡处理。   
  117.                         case RH:{   
  118.                             System.out.println("[RH=-1 ——> EH=0]. 没有不平衡现象");   
  119.                             node.bFactor=BalanceFactor.EH;   
  120.                             isTaller=false;   
  121.                             break;   
  122.                         }   
  123.                     }//end switch   
  124.                 }//end if   
  125.             }//end if   
  126.             //右子树搜索   
  127.             else{   
  128.                 if(node.rchild==null){   
  129.                     System.out.println("].  插入到"+node.key+"的右孩子");   
  130.                     AVLNode<E> newNode=new AVLNode<E>(key);   
  131.                     node.rchild=newNode; //设置右孩子结点   
  132.                     newNode.parent=node; //设置父亲结点   
  133.                     isTaller=true//树长高了   
  134.                 }   
  135.                 else{   
  136.                     insertAVL(key,node.rchild);   
  137.                 }   
  138.                 //当前如果树长高了,说明是因为右孩子的添加改变了平衡因子(右高)。   
  139.                 if(isTaller){   
  140.                     System.out.print("          树变化了,"+node.key+"的平衡因子变化");   
  141.                     switch(node.bFactor){   
  142.                         //原来结点平衡因子是LH(bf=1),则右高以后bf=0,不需要平衡处理。   
  143.                         case LH: {   
  144.                             System.out.println("[LH=1 ——> EH=0]. 没有不平衡现象");   
  145.                             node.bFactor=BalanceFactor.EH;   
  146.                             isTaller=false;   
  147.                             break;   
  148.                         }   
  149.                         //原来结点平衡因子是EH(bf=0),则右高了以后bf=-1,不需要平衡处理。   
  150.                         case EH:{   
  151.                             System.out.println("[EH=0 ——> RH=-1]. 没有不平衡现象");   
  152.                             node.bFactor=BalanceFactor.RH;   
  153.                             isTaller=true;   
  154.                             break;   
  155.                         }   
  156.                         //原来结点平衡因子是RH(bf=-1),则右高以后bf=0,因此需要做右平衡旋转。   
  157.                         case RH:{   
  158.                             System.out.println("[RH=-1 ——> RH=-2]. 出现了不平衡现象[左比右矮2]");   
  159.                             rightBalance(node);   
  160.                             isTaller=false;    
  161.                             break;   
  162.                         }   
  163.                     }//end switch   
  164.                 }//end if(isTaller)   
  165.             }//end else   
  166.             return true;   
  167.         }//end else   
  168.     }   
  169.     /**  
  170.      * 左平衡旋转处理  
  171.      * 先对node的左子树进行单左旋处理,在对node树进行单右旋处理  
  172.      *   
  173.      *     100                      100                     90  
  174.          *     /  \           左旋       /  \          右旋     /  \  
  175.          *    80  120   ------>  90  120   ------> 80  100    
  176.          *   / \                         /                        /  \     \  
  177.          *  60 90                   80                     60  85  120  
  178.          *     /                        / \  
  179.          *    85                    60 85  
  180.      *   
  181.      * @param node 需要做处理的子树的根结点  
  182.      */  
  183.     private void leftBalance(AVLNode<E> node){   
  184.         // node.parent指向新的孩子结点   
  185.         AVLNode<E> lc=node.lchild;//lc指向node的左孩子结点   
  186.         switch(lc.bFactor){   
  187.             case LH:{  //新结点插入在node的左孩子的左子树上,则需要单右旋处理   
  188.                 System.out.println("           ┖ 对"+node.key+"进行单右旋转处理");   
  189.                 node.bFactor=lc.bFactor=BalanceFactor.EH;   
  190.                 rRotate(node);   
  191.                 break;   
  192.             }   
  193.             case RH:{  //新结点插入在node的左孩子的右子树上,需要双旋处理   
  194.                 System.out.println("            ┖ 对"+node.key+"的左子树进行单左旋转处理,再对其本身树进行单右循环处理");   
  195.                 AVLNode<E> rd=lc.rchild; //rd指向node左孩子的右子树根   
  196.                 switch(rd.bFactor){ //修改node与其左孩子的平衡因子   
  197.                     case LH:{   
  198.                         node.bFactor=BalanceFactor.RH;   
  199.                         lc.bFactor=BalanceFactor.EH;   
  200.                         break;   
  201.                     }   
  202.                     case EH:{   
  203.                         node.bFactor=lc.bFactor=BalanceFactor.EH;   
  204.                         break;   
  205.                     }   
  206.                     case RH:{   
  207.                         node.bFactor=BalanceFactor.EH;   
  208.                         lc.bFactor=BalanceFactor.LH;   
  209.                         break;   
  210.                     }   
  211.                 }//switch   
  212.                 rd.bFactor=BalanceFactor.EH;   
  213.                 lRotate(node.lchild);   
  214.                 rRotate(node);   
  215.                 break;   
  216.             }   
  217.         }   
  218.            
  219.     }   
  220.     /**  
  221.      * 右平衡旋转处理  
  222.      *   
  223.      *    80                         80                        85    
  224.          *   /  \            右 旋      /  \        左 旋        /  \       
  225.          *  60  100    ------>  60   85   ------->   80  100  
  226.          *      /  \                       \                       /   /  \         
  227.          *     85  120                100                 60  90  120  
  228.          *      \                          /  \  
  229.          *      90                     90  120   
  230.      *   
  231.      * @param node  
  232.      */  
  233.     private void rightBalance(AVLNode<E> node){   
  234.         AVLNode<E> lc=node.rchild;//lc指向node的右孩子结点   
  235.         switch(lc.bFactor){   
  236.             case RH:{  //新结点插入在node的右孩子的右子树上,则需要单左旋处理   
  237.                 node.bFactor=lc.bFactor=BalanceFactor.EH;   
  238.                 lRotate(node);   
  239.                 break;   
  240.             }   
  241.             case LH:{  //新结点插入在node的右孩子的左子树上,需要双旋处理   
  242.                 AVLNode<E> rd=lc.lchild; //rd指向node右孩子的左子树根   
  243.                 switch(rd.bFactor){ //修改node与其右孩子的平衡因子   
  244.                     case LH:{   
  245.                         node.bFactor=BalanceFactor.EH;   
  246.                         lc.bFactor=BalanceFactor.RH;   
  247.                         break;   
  248.                     }   
  249.                     case EH:{   
  250.                         node.bFactor=lc.bFactor=BalanceFactor.EH;   
  251.                         break;   
  252.                     }   
  253.                     case RH:{   
  254.                         node.bFactor=BalanceFactor.LH;   
  255.                         lc.bFactor=BalanceFactor.EH;   
  256.                         break;     
  257.                     }   
  258.                 }//switch   
  259.                 rd.bFactor=BalanceFactor.EH;   
  260.                 rRotate(node.rchild);   
  261.                 lRotate(node);   
  262.                 break;   
  263.             }   
  264.         }   
  265.     }   
  266.        
  267.        
  268.     /**  
  269.      * 对以node为根的子树进行单右旋处理,处理后node.parent指向新的树根,即旋转之前  
  270.      * node的左孩子结点  
  271.      *      100<-node.parent           80<-node.parent  
  272.      *      /                                      /  \  
  273.      *     80             ———>         60   100  
  274.      *    /  \                                  /  
  275.      *   60  85                            85  
  276.      */  
  277.     private void rRotate(AVLNode<E> node){   
  278.            
  279.         AVLNode<E> lc=node.lchild;//lc指向node的左孩子结点   
  280.            
  281.         node.lchild=lc.rchild;   
  282.         lc.rchild=node;   
  283.         if(node.parent==null){   
  284.             root=lc;   
  285.         }   
  286.         else if(node.parent.lchild.key.compareTo(node.key)==0)   
  287.             node.parent.lchild=lc;   
  288.         else node.parent.rchild=lc;   
  289.     }   
  290.     /**  
  291.      * 对以node为根的子树进行单左旋处理,处理后node.parent指向新的树根,即旋转之前  
  292.      * node的右孩子结点  
  293.      *      100<-node.parent        110<-node.parent  
  294.      *        \                                  /  \  
  295.      *        110        ————>   100  120  
  296.      *        /  \                               \  
  297.      *      105  120                      105  
  298.      */  
  299.     private void lRotate(AVLNode<E> node){   
  300.         AVLNode<E> rc=node.rchild;//lc指向node的右孩子结点   
  301.         node.rchild=rc.lchild;   
  302.         rc.lchild=node;   
  303.         if(node.parent==null){   
  304.             root=rc;   
  305.                
  306.         }   
  307.         else if(node.parent.lchild.key.compareTo(node.key)==0)   
  308.                 node.parent.lchild=rc;   
  309.         else node.parent.rchild=rc;   
  310.     }   
  311.        
  312.     /**  
  313.      * 得到BST根节点  
  314.      * @return BST根节点f  
  315.      */  
  316.     public AVLNode<E> getRoot(){   
  317.         return this.root;   <
    分享到:
    评论

相关推荐

    C#,自平衡二叉查找树(AVL Tree)的算法与源代码

    C#,自平衡二叉查找树(AVL Tree)的算法与源代码 自平衡二叉查找树(AVL Tree)中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL...

    AVL树数据结构平衡二叉查找树

    在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...

    平衡二叉查找树算法代码

    平衡二叉查找树代码 AVL 二叉树 查找树

    GNU的自平衡二叉查找树(AVL tree、redblack tree等)源代码

    GNU的自平衡叉查找树的源代码库,包括AVL teee和红黑树 redblack tree、二叉查找树。还有PDF的原理说明及HTML的源代码函数解释。

    二叉查找树代码(avl,bst,rbt,sbt,splay,treap树)

    avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...

    二叉树排序树建立及平衡处理

    在根指针T所指的平衡二叉排序树中递归的查找其元素值等于e的数据元素, 若查找成功,则指针p指向该数据元素结点,并返回TRUE,否则指针p 指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲, 其初始...

    2.22.AVL树_C语言_二叉查找树_

    在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是。增加和删除可能需要通过一...

    二叉查找树,AVL树

    AVL树(平衡二叉查找树) 具有二叉查找树的全部特性。 每个节点的左子树的高度和右子树高度差值小于等于1(平衡二叉树的性质) 左旋:逆时针旋转两个节点,原先的右节点成为新的父节点,原先的父节点成为原先的右...

    c代码-平衡二叉查找树 --AVL树

    c代码-平衡二叉查找树 --AVL树

    C++数据结构-二叉查找树和平衡二叉树

    实现了二叉查找树的查找、插入...实现了平衡二叉树(AVL树)的查找、插入、删除和迭代遍历的完整功能,插入时的各种旋转操作按照经典数据结构教材实现,并有详细的注释和说明。删除操作和相关旋转方法有单独描述文档。

    二叉排序树与平衡二叉树的实现

    平衡二叉排序树的在平衡因子绝对值等于2时开始调整到绝对值为1或0,在平衡因子绝对值为2时,二叉排序树会出现四种不同的情况的树形,因此这时需要分别单独讨论来降低平衡因子。 1.2.7 平衡二叉树的调整方法  平衡...

    常见的二叉搜索树的实现代码

    常见的二叉搜索树的实现代码,包括平衡二叉排序树,红黑树等

    二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造 课设作业 完整代码

    平衡二叉树(Balanced Binary Tree)又被称为AVL树。具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的: 二叉排序树的实现...

    数据结构之AVL树详解

    有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树(Left),导致根节点的平衡因子由1变为2 (2)RR:插入一个新节点到根节点的右子树(Right

    数据结构与算法的介绍及应用

    二叉排序树查找,Python3 数据结构与算法的... 查找算法: 顺序查找、二分查找、哈希表查找、二叉查找树、平衡二叉查找树(AVL树、红黑树)、平衡多路查找树(B树、B+树);4. LeetCode 和《剑指Offer》刷题、多种方法的题解

    c语言平衡二叉树代码示例

    平衡二叉树 平衡二叉树(Balanced ...AVL是最先发明的自平衡二叉查找树算法,在AVL中任何节点的两个儿子子树的高度最大差别为一,所以它也被称为高度平衡树。 查找、插入和删除在平均和最坏情况下都是O(log n)。

    数据结构实验(单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序)的实现

    单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序等共四个实验的实现过程。

    AVL Tree source code

    AVL Tree source code

Global site tag (gtag.js) - Google Analytics