手机版
你好,游客 登录 注册
背景:
阅读新闻

数据结构 - (AVL)平衡二叉树

[日期:2019-03-03] 来源:Linux社区  作者:Jzedy [字体: ]

AVL树本质上还是二叉树,但是比二叉搜索树多了一个条件:每个节点的左右子树高度不超过1
因为二叉搜索树在极端情况下无限趋近于链表,这种情况下不能体现二叉搜索树的高效率。如下图

数据结构 - (AVL)平衡二叉树

{
     Node<T> root;
    
    {
         T key;
         Node<T> left;
         Node<T> right;


        {
            .key = key;
        }
    }
}
{
     height(root);
}

{
    ;
     {
        ;
    }
}

AVL树在添加或者删除后,可能导致AVL树失去平衡。
失去平衡包括四种:LL(左左),LR(左右),RR(右右),RL(右左),具体参考下图

数据结构 - (AVL)平衡二叉树

数据结构 - (AVL)平衡二叉树

数据结构 - (AVL)平衡二叉树

旋转方式:将k1变成根节点,k2变成k1的右子树,"k1的右子树"变成"k2的左子树"

/**
* 左左旋转
* @param tree
* @return
*/
> tree){
 ;
 tree.;
 lTree. = tree;
  lTree;
}

数据结构 - (AVL)平衡二叉树

旋转方式:旋转方式与LL旋转类似

/**
 * 右右旋转
 * @param tree
 * @return
 */
> tree){
    ;
    tree.;
    rTree. = tree;
     rTree;
}

数据结构 - (AVL)平衡二叉树

旋转方式:左右旋转需要经过两次调整,第一次旋转是围绕"k1"进行的"RR旋转",第二次是围绕"k3"进行的"LL旋转"

/**
 * 左右旋转
 *  tree
 * 
 */
{
    rrRotation(tree.left);
     llRotation(tree);
}

数据结构 - (AVL)平衡二叉树

旋转方式:右左旋转同样需要经过两次调整,第一次旋转是围绕"k3"进行的"LL旋转",第二次是围绕"k1"进行的"RR旋转"

/**
 * 右右旋转
 *  tree
 * 
 */
{
    llRotation(tree.right);
     rrRotation(tree);
}
{
    ){
        root =  Node<>(key);
    } {
        
        root = fixAfterOperation(root);
    }
}

{
     tmp;
    ){
        tree =  Node<>(key);
    } {
        tmp = key.compareTo(tree.key);
        ){
            tree.left = (tree.left,key);
        }){
            tree.right = (tree.right,key);
        } {
             tree;
        }
    }
     tree;
}

当树添加或者删除某一节点后,如果导致AVL树失衡,旋转树

> tree) {
     (tree != null) {
        
            
                tree = llRotation(tree);
            } 
                tree = lrRotation(tree);
            }

        }

        
            
                tree = rlRotation(tree);
            }  {
                tree =rrRotation(tree);
            }
        }
    }
     tree;
}
{
    ){
        (root,key);
        root = fixAfterOperation(root);
    }
}

{
     tree;
     tmp = key.compareTo(tree.key);
    ){
        tree.left = (tree.left,key);
    }){
        tree.right = (tree.right,key);
    } {
            Node<T> successor = successor(tree);
            
                Node<T> l = tree.left;
                
                    tree = ;
                }
                    tree.key = l.key;
                    tree.left = (tree.left,l.key);
                }
            }
                tree.key = successor.key;
                tree.right = (tree.right,successor.key);
            }
    }
     tree;
}


{
    Node<T> result = tree.right;
    ){
        result = result.left;
    }
     result;
}

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-03/157249.htm

linux
相关资讯       AVL平衡二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款