为什么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
代码参考：
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），为其创建了填充输入值的节点对象，那么它不能通过上述定义就地调用，即使在过程结束时值被复制回输入数组。
作为比较，堆排序不需要创建新的数据结构，因为输入数组可用于将其值重新组织到堆中。它只需交换该数组中的值即可对其进行排序。因此它是一种就地算法。
最近听说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
代码参考：
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），为其创建了填充输入值的节点对象，那么它不能通过上述定义就地调用，即使在过程结束时值被复制回输入数组。
作为比较，堆排序不需要创建新的数据结构，因为输入数组可用于将其值重新组织到堆中。它只需交换该数组中的值即可对其进行排序。因此它是一种就地算法。