设为首页 加入收藏

TOP

深入理解平衡二叉树AVL与Python实现(一)
2019-02-10 22:08:37 】 浏览:66
Tags:深入 理解 平衡 AVL Python 实现

像这样:



如果先插入10,再插入20,再插入30,再插入40就会成上边这个样子


这个就像是双向链表,我们期望它是下面这个样子:



所以我们希望有一种策略能够将第一个图变成第二个图,或者说使树的结构不会产生像第一种图的形式


实现这种策略的一种方式是AVL树


AVL树的名称是以它的发明家的名字命名的:Adel’son-Vel’skii和Landis


满足高度平衡属性的二叉树就是AVL树


高度平衡属性是:对于树中的每一个位置p,p的孩子的高度最多相差1


很显然前言中的第一个图并不满足高度平衡属性,第二个是满足的。


同时高度平衡属性也意味着一颗AVL树的子树同样是AVL树


并且可以通过证明(这里就不再证了)得到AVL树的高度是O(log n)


所以得出结论,AVL树可以使时间复杂度保持O(log n)


接下来的问题就是怎样保持二叉树的高度平衡属性


要保持高度平衡属性的原因是破坏了高度平衡属性


破坏的方式有两种:添加节点与删除节点


添加节点如图:



添加50的时候,就会破坏高度平衡属性


删除节点如图:



删除10的时候也会破坏高度平衡属性


最后,不论是添加节点还是删除节点,都会使树变成非高度平衡的状态,这种非高度平衡的状态有4种:



LL是left-left,可以理解为:首先它不平衡,其次根节点的左子树比右子树高,并且根节点的左子树的左子树比根节点的左子树的右子树高。(从上到下都是左边高)



LR是left-right,可以理解为:首先它不平衡,其次根节点的左子树比右子树高,并且根节点的左子树的右子树比根节点的左子树的左子树高。(从上到下先左高后右高)



RR是right-right,可以理解为:首先它不平衡,其次根节点的右子树比左子树高,并且根节点的右子树的右子树比根节点的右子树的左子树高。(从上到下都是右边高)



RL是right-left,可以理解为:首先它不平衡,其次根节点的右子树比左子树高,并且根节点的右子树的左子树比根节点的右子树的右子树高。(从上到下先右高后左高)


最后,判断是哪种形式的非平衡状态,一定要从不平衡的节点位置看,并不是看4层,比如:



这里只有3层节点,不平衡的节点是20,20的左子树比右子树高,10的左子树比右子树高,所以是LL。(这里的高定义为节点5的高度为1,空节点的高度为0)


接下来是保持高度平衡的调整策略:


同样对于4种不同的形式有4种解决方案:



这个变换就像是以10为中心,向右旋转,使10变成根节点,10的左子树不变,右子树变成了20,多余出的15正好挂在由于变换失去了左子树的20的左边。变换后结点从左到右的顺序依然没有变,所以15是正好挂在20的左边的。



RR与LL形式差不多,只不顾是反着来的。相当于进行一次左旋转。


RR与LL都只进行一次旋转即可,而LR与RL需要进行两次旋转



第一次相当于对5、10、15、17这棵子树进行了一次RR旋转,旋转方式与之前的RR方式相同,就像是以15为中心向左旋转,旋转的结果使得整棵树变成了LL的不平衡形态,然后再按照LL的旋转方式对整棵树处理。



RL同样是LR的相反模式,先将22、25、30、40这棵子树进行LL旋转,再将整棵树进行RR旋转


理解了avl保持平衡从方式后,就可以用代码来实现了


我们使用AVL对上一篇文章中的有序映射进行优化


因为AVL依赖于节点的高度,所以首先要重写一下Node类:


class AvlTree(OrderedMap):


    class Node(OrderedMap.Node):
        def __init__(self, element, parent=None, left=None, right=None):
            super().__init__(element,parent,left,right)
            self.height = 0


        def left_height(self):
            return self.left.height if self.left is not None else 0


        def right_height(self):
            return self.right.height if self.right is not None else 0


接下来定义4中调整的非公开方法


def _left_left(self,p):
    this = p.node        # 有变化的就4个节点
    left = this.left
    parent = this.parent
    left_right = this.left.right
    if parent is not None:
        if this is parent.left:
            parent.left = left
        else:
            parent.right = left
    else:
        self._root = left
    this.parent = left
    left.parent = parent
    this.left = left_right
    left.right = this
    if left_right is not None:
        left_right.parent = this


def _right_right(self,p):
    this = p.node                # 有变化的就4个节点
    right = this.right
    parent = this.parent
    right_left = this.right.left
    if parent is not None:
        if this is parent.left:
            parent.left = right
        else:
            parent.right = right
    else:
        self
编程开发网

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Java设计模式之策略模式 下一篇Java设计模式之观察者模式

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }