Я создал алгоритм, цель которого должна быть, учитывая два узла A и B в BST, он переключает роли (или позиции в дереве) этих двух, просто перемещая указатели. В моем представлении BST я использую двойное связанное соединение (т.е. A.parent == B и (B.left == A) или (B.right == A)). Я не уверен, полностью ли он исправлен или нет. Я разделил алгоритм в двух ситуациях.
-
A и B напрямую связаны (либо A является родителем B, либо B родителем A)
-
Все остальные случаи
Для каждого из предыдущих случаев я создал вложенную функцию. Я хотел бы получить ваше мнение о первом правильности алгоритмов, и если можно каким-то образом улучшить его. Здесь код:
def switch(self, x: BSTNode, y: BSTNode, search_first=False):
if not x:
raise ValueError("x cannot be None.")
if not y:
raise ValueError("y cannot be None.")
if x == y:
raise ValueError("x cannot be equal to y")
if search_first:
if not self.search(x.key) or not self.search(y.key):
raise LookupError("x or y not found.")
def switch_1(p, s):
"""Switches the roles of p and s,
where p (parent) is the direct parent of s (son)."""
assert s.parent == p
if s.is_left_child():
p.left = s.left
if s.left:
s.left.parent = p
s.left = p
s.right, p.right = p.right, s.right
if s.right:
s.right.parent = s
if p.right:
p.right.parent = p
else:
p.right = s.right
if s.right:
s.right.parent = p
s.right = p
s.left, p.left = p.left, s.left
if s.left:
s.left.parent = s
if p.left:
p.left.parent = p
if p.parent:
if p.is_left_child():
p.parent.left = s
else:
p.parent.right = s
else: # p is the root
self.root = s
s.parent = p.parent
p.parent = s
def switch_2(u, v):
"""u and v are nodes in the tree
that are not related by a parent-son
or a grandparent-son relantionships."""
if not u.parent:
self.root = v
if v.is_left_child():
v.parent.left = u
else:
v.parent.right = u
elif not v.parent:
self.root = u
if u.is_left_child():
u.parent.left = v
else:
u.parent.right = v
else: # neither u nor v is the root
if u.is_left_child():
if v.is_left_child():
v.parent.left, u.parent.left = u, v
else:
v.parent.right, u.parent.left = u, v
else:
if v.is_left_child():
v.parent.left, u.parent.right = u, v
else:
v.parent.right, u.parent.right = u, v
v.parent, u.parent = u.parent, v.parent
u.left, v.left = v.left, u.left
u.right, v.right = v.right, u.right
if u.left:
u.left.parent = u
if u.right:
u.right.parent = u
if v.left:
v.left.parent = v
if v.right:
v.right.parent = v
if x.parent == y:
switch_1(y, x)
elif y.parent == x:
switch_1(x, y)
else:
switch_2(x, y)
Мне действительно нужно, чтобы switch работал во всех случаях независимо от того, какие узлы x или y мы выберем. Я уже провел некоторые тесты, и, похоже, это работает, но я все еще не уверен.
ИЗМЕНИТЬ
В конце концов, если это будет полезно как-то, здесь у вас есть полная реализация моего BST (с тестами, которые я делаю):
РЕДАКТИРОВАТЬ 2 (просто любопытство)
@Ришав прокомментировал:
Я не понимаю намерения этой функции. Если нужно обменять два узла в BST, недостаточно ли их обмена данными вместо того, чтобы манипулировать указателями?
Я ответил:
Хорошо, возможно, я должен был добавить немного больше о причине всей этой "монстра". Я могу вставлять объекты
BSTNodeили любые сопоставимые объекты в свой BST. Когда пользователь решает вставить какой-либо сопоставимый объект, ответственность за созданиеBSTNodeпринадлежит мне, поэтому пользователь не имеет доступа к исходной ссылкеBSTNode, если только они не ищут ключ. НоBSTNodeбудет возвращен только после вставки ключа, или в нем уже есть другой объектBSTNodeс тем же ключом (или значением), но этот последний случай не имеет значения.Пользователь также может вставить объект
BSTNodeв дерево, у которого есть начальный (и должен оставаться постоянным) ключ (или значение). Тем не менее, если бы я просто обменял значения или ключи узлов, у пользователя была бы ссылка на node с другим ключом, а затем на ключ node, который он вставил. Конечно, я хочу этого избежать.
