为什么AVL排序不到位?

Why AVL sort is not in place?

最近听说AVL排序不到位。谁能解释一下?从下面的代码中,我不确定在排序时我在哪里分配了额外的 space 。在此代码中,当构建数据结构或插入元素时,元素按其键排序。

声明参考:他们正在使用此声明来激发“二进制堆”

[1].https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/MIT6_006S20_r08.pdf

代码参考:

[2]。 https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/MIT6_006S20_r06.pdf

[3]。 https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/MIT6_006S20_r07.pdf

def height(A):
    if A: return A.height
    else: return -1

class Binary_Node:
    def __init__(self, x):
        self.item = x
        self.parent = None
        self.left = None
        self.right = None
        self.subtree_update()

    def subtree_update(self):
        self.height = 1 + max(height(self.left), height(self.right))

    def subtree_iter(self):
        if self.left: yield from self.left.subtree_iter()
        yield self
        if self.right: yield from self.right.subtree_iter()
        
    def subtree_first(self):
        if self.left: return self.left.subtree_first()
        else: return self
    
    def subtree_last(self):
        if self.right: return self.right.subtree_last()
        else: return self
        
    def sucessor(self):
        if self.right: return self.right.subtree_first()
        while self.parent and (self is self.parent.right): #A is parent's left child and A's parent exists
            self = self.parent
        return self.parent
        
    def predecessor(self):
        if self.left: return self.left.subtree_last()
        while self.parent and (self is self.parent.left):
            self = self.parent
        return self.parent
    
    def subtree_insert_before(self, A):
        if self.left: 
            self = self.left.subtree_last()
            self.right, A.parent = A, self
        else: 
            self.left, A.parent = A, self
        self.maintain()
        
    def subtree_insert_after(self, A):
        if self.right: 
            self = self.right.subtree_first()
            self.left, A.parent = A, self
        else: 
            self.right, A.parent = A, self
        self.maintain()
        
    def delete(self):
        if not self.left and not self.right: # when self is leaf
            if self.parent: 
                A = self.parent
                if A.left is self: A.left = None
                else: A.right = None
                self.parent = None
            
        if self.left: 
            self.item, self.left.subtree_last().item = self.left.subtree_last().item, self.item
            self.left.subtree_last().delete()
        
        else:
            self.item, self.right.subtree_first().item = self.right.subtree_first().item, self.item
            self.right.subtree_last().delete()
            
    def subtree_delete(self):
        if self.left or self.right:
            if self.left: B = self.predecessor()
            else: B = self.sucessor()
            self.item, B.item = B.item, self.item
            return B.subtree_delete()
            
        if self.parent:
            if self.parent.left is self: self.parent.left = None
            else: self.parent.right = None
            self.parent.maintain()
        return self
    
    def subtree_rotate_right(self):
        assert self.left
        B, E = self.left, self.right
        A, C = B.left, B.right
        B, self = self, B
        self.item, B.item = B.item, self.item
        B.left, B.right = A, self
        self.left, self.right = C, E
        if A: A.parent = B
        if E: E.parent = self
        B.subtree_update()
        self.subtree_update()
    
    def subtree_rotate_left(self):
        assert self.right
        A, D = self.left, self.right
        C, E = D.left, D.right
        self, D = D, self
        self.item, D.item = D.item, self.item
        self.left, self.right = A, C
        D.left, D.right = self, E
        if A: A.parent = self
        if E: E.parent = D
        self.subtree_update()
        D.subtree_update()
    
    def skew(self):
        return height(self.right) - height(self.left)
    
    def rebalance(self):
        if self.skew() == 2:
            if self.right.skew() < 0:
                self.right.subtree_rotate_right()
            self.subtree_rotate_left()
        elif self.skew() == -2:
            if self.left.skew() > 0:
                self.left.subtree_rotate_left()
            self.subtree_rotate_right()
    
    def maintain(self):
        self.rebalance()
        self.subtree_update()
        if self.parent: self.parent.maintain()
    
class Binary_Tree:
    def __init__(self, Node_Type = Binary_Node):
        self.root = None
        self.size = 0
        self.Node_Type = Node_Type
        
    def __len__(self): return self.size
    def __iter__(self):
        if self.root:
            for A in self.root.subtree_iter():
                yield A.item 
        
    def build(self, X):
        A = [x for x in X]
        def build_subtree(A, i, j):
            c = (i + j) // 2
            root = self.Node_Type(A[c])
            if i < c:
                root.left = build_subtree(A, i, c - 1)
                root.left.parent = root
            if j > c:
                root.right = build_subtree(A, c + 1, j)
                root.right.parent = root
            return root
        self.root = build_subtree(A, 0, len(A) - 1)
        
        
class BST_Node(Binary_Node):
    def subtree_find(self, k):
        if self.item.key > k:
            if self.left: self.left.subtree_find(k)
        elif self.item.key < k:
            if self.right: self.right.subtree_find(k)
        else: return self
        
        return None
    
    
    def subtree_find_next(self, k):
        if self.item.key <= k:
            if self.right: return self.right.subtree_find_next(k)
            else: return None
            
        elif self.item.key > k:
            if self.left: return self.left.subtree_find_next(k)
            else: return self 
        
        return self
        
    
    def subtree_find_prev(self, k):
        if self.item.key >= k:
            if self.left: return self.left.subtree_find_prev(k)
            else: return None
        elif self.item.key < k:
            if self.right: return self.right.subtree_find_prev(k)
            else: return self
        
        return self
    
    def subtree_insert(self, B):
        if B.item.key < self.item.key:
            if self.left: self.left.subtree_insert(B)
            else: self.subtree_insert_before(B)
        
        elif B.item.key > self.item.key:
            if self.right: self.right.subtree_insert(B)
            else: self.subtree_insert_after(B)
        
        else:
            self.item = B.item
        
        
class Set_Binary_Tree(Binary_Tree):
    def __init__(self): super().__init__(BST_Node)

    def iter_order(self): yield from self
    
    def build(self, X):
        for x in X: self.insert(x)
    
    def find_min(self): 
        if self.root: return self.root.subtree_first()
        
    def find_max(self): 
        if self.root: return self.root.subtree_last()
        
    def find(self, k):
        if self.root: 
            node = self.root.subtree_find(k)
            if node:
                return node.item
        
    def find_next(self, k): 
        if self.root:
            node = self.root.subtree_find_next(k)
            if node:
                return node.item
            
            
    def find_prev(self, k): 
        if self.root:
            node = self.root.subtree_find_prev(k)
            if node:
                return node.item
        
    def insert(self, x): 
        new = self.Node_Type(x)
        if self.root:
            self.root.subtree_insert(new)
            if new.parent is None: return False
            
        else:
            self.root = new
        
        self.size += 1
        return True
        
        
    def delete(self, k):
        assert self.root
        node = self.root.subtree_find(k)
        assert node
        ext = node.subtree_delete()
        if ext.parent is None: self.root = None
        self.size -= 1
        return ext.item

Wikipedia定义了一个in-place算法如下:

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. An in-place algorithm updates its input sequence only through replacement or swapping of elements.

因此,称为“就地”的算法的属性之一是它不会将所有输入值复制到新分配的数据结构中。如果一个算法创建了一个二叉搜索树(如 AVL),为其创建了填充输入值的节点对象,那么它不能通过上述定义就地调用,即使在过程结束时值被复制回输入数组。

作为比较,堆排序不需要创建新的数据结构,因为输入数组可用于将其值重新组织到堆中。它只需交换该数组中的值即可对其进行排序。因此它是一种就地算法。