#algorithm #sorting #avl-tree #in-place
#алгоритм #сортировка #avl-дерево #на месте
Вопрос:
Недавно мне сказали, что AVL-сортировка не на месте. Может кто-нибудь, пожалуйста, объяснить это? Из приведенного ниже кода я не уверен, где я назначаю дополнительное пространство при сортировке. В этом коде, когда создается структура данных или вставляется элемент, элементы упорядочиваются по их ключу.
Ссылка на утверждение: они используют это утверждение для мотивации «двоичной кучи»
[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
Комментарии:
1. Пожалуйста, укажите ваш источник.
2. Пожалуйста, добавьте ссылки для обоих утверждений. Кто сказал, что он выполняется в постоянном пространстве, а кто говорит иначе.
3. Пожалуйста, нарисуйте, как работает AVL-сортировка и как она использует пространство для хранения (гиперссылки приветствуются для справки и деталей ). Кажется, я помню деревья AVL.
4. Если верить Google, сортировка AVL начинается с несортированного массива. Затем вы строите дерево AVL из элементов массива. Наконец, выполните обход дерева AVL по порядку, поместив элементы обратно в массив. Вполне возможно, что это худшая сортировка O (NlogN), когда-либо задуманная с точки зрения времени выполнения. Время разработки также является обременительным, если у вас уже нет кода AVL.
5. @user3386109 Вот оно. Вы строите дерево AVL. Это не на месте. «На месте» означает «внутри массива». Но дерево AVL не находится «внутри массива».
Ответ №1:
Википедия определяет алгоритм на месте следующим образом:
В информатике алгоритм на месте — это алгоритм, который преобразует входные данные, не используя вспомогательную структуру данных. Однако для вспомогательных переменных допускается небольшое дополнительное пространство для хранения. Входные данные обычно перезаписываются выходными данными по мере выполнения алгоритма. Алгоритм на месте обновляет свою входную последовательность только путем замены или замены элементов.
Итак, одним из свойств алгоритма, который называется «на месте», является то, что он не копирует все входные значения во вновь выделенную структуру данных. Если алгоритм создает двоичное дерево поиска (например, AVL), для которого создаются объекты узла, заполненные входными значениями, то он не может быть вызван на месте по приведенному выше определению, даже если в конце процесса значения копируются обратно во входной массив.
Для сравнения, при сортировке по куче не нужно создавать новую структуру данных, поскольку входной массив можно использовать для преобразования его значений в кучу. Он просто должен поменять местами значения в этом массиве, чтобы отсортировать его. Следовательно, это алгоритм на месте.