深入理解平衡二叉树AVL与Python实现(3)

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种平衡策略时，一定要记着将整棵树的根节点更新，不然遍历的时候，根节点指的就不是真正的根节点了。

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