当前位置: 萬仟网 > IT编程>脚本>Python > 详细理解平衡二叉树AVL与Python实现

详细理解平衡二叉树AVL与Python实现

2019年02月11日 07:17  | 萬仟网IT编程  | 我要评论

前言

上一篇文章讨论的二叉搜索树,其时间复杂度最好的情况下是o(log(n)),但是最坏的情况是o(n),什么时候是o(n)呢?

像这样:

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

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

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

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

avl树

avl树的名称是以它的发明家的名字命名的:adel’son-vel’skii和landis

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

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

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

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

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

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

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

保持二叉树的高度平衡属性

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

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

添加节点如图:

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

删除节点如图:

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

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

1.ll

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

2.lr

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

3.rr

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

4.rl

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

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

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

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

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

1.ll

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

2.rr

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

rr与ll都只进行一次旋转即可,而lr与rl需要进行两次旋转

3.lr

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

4.rl

rl同样是lr的相反模式,先将22、25、30、40这棵子树进行ll旋转,再将整棵树进行rr旋转

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

python实现

我们使用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._root = right
    this.parent = right
    right.parent = parent
    this.right = right_left
    right.left = this
    if right_left is not none:
        right_left.parent = this

def _left_right(self,p):
    self._right_right(self.left(p))
    self._left_left(p)

def _right_left(self,p):
    self._left_left(self.right(p))
    self._right_right(p)

然后是用于平衡二叉树的方法,也就是根据情况调用上边那4种策略

def _isbalanced(self,p):
    """判断节点是否平衡"""

    return abs(p.node.left_height() - p.node.right_height()) <= 1

def _recompute_height(self,p):
    """重新计算高度"""
    p.node.height = 1 + max(p.node.left_height(),p.node.right_height())

def _rebalanced(self,p):
    while p is not none:
        if self._isbalanced(p):
            self._recompute_height(p)
            p = self.parent(p)
        else:

            if p.node.left_height()>p.node.right_height() and p.node.left.left_height()>p.node.left.right_height():
                # ll的情况,只有自己和左孩子的高度可能变化
                self._left_left(p)
            elif p.node.right_height()>p.node.left_height() and p.node.right.right_height()>p.node.right.left_height():
                # rr的情况,只有自己和右孩子的高度可能变化
                self._right_right(p)
            elif p.node.left_height()>p.node.right_height() and p.node.left.left_height()<p.node.left.right_height():
                # lr的情况,只有自己和左孩子和左孩子的右孩子的高度可能变化
                left = self.left(p)
                self._left_right(p)
                self._recompute_height(left)
            else:
                # rl的情况,只有自己和右孩子和右孩子的左孩子的高度可能变化
                right = self.right(p)
                self._right_left(p)
                self._recompute_height(right)
            while p is not none:
                # 调整所有p的祖先的高度
                self._recompute_height(p)
                p = self.parent(p)

然后把方法封装成删除时和插入时的两个方法,虽然执行的内容是相同的

def _rebalanced_insert(self,p):
    """插入时的平衡调整"""
    self._rebalanced(p)

def _rebalanced_delete(self, p):
    """删除时的平衡调整"""
    self._rebalanced(p)

最后重写一下setitem方法与删除时调用的方法

def __setitem__(self, k, v):
    """优化setitem"""
    if self.is_empty():
        leaf = self.add_root(self._item(k, v))
    else:

        p = self._subtree_search(self.root(), k)
        if p.key() == k:
            p.element().value = v
            return
        else:
            item = self._item(k, v)
            if p.key() < k:
                leaf = self.add_right(p, item)
            else:
                leaf = self.add_left(p, item)
    self._rebalanced_insert(leaf)

def mapdelete(self, p):
    if self.left(p) and self.right(p):  # 两个孩子都有的时候
        replacement = self._subtree_last_position(
            self.left(p))  # 用左子树最右位置代替
        self.replace(p, replacement.element())
        p = replacement
    parent = self.parent(p)
    self.delete(p)
    self._rebalanced_delete(parent)

在实现4种平衡策略时,一定要记着将整棵树的根节点更新,不然遍历的时候,根节点指的就不是真正的根节点了。

您可能感兴趣的文章:

如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复

相关文章:

◎已有 0 人评论

Copyright © 2019  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com