К сожалению, вы не предоставите намкласса, но давайте предположим, что это что-то вроде:
class Tree(object):
def __init__(self):
self.data = None
self.nextkey = 0
self.thedict = {}
с различными атрибутами обновляются точно, когда новые узлы вставляются. Теперь, когда вы говорите об «адресе, сохраненном в словаре», ясно, что значение dict не является «адресом» - скорее, это объект Node (если вы определяете специальный метод __repr__ в своем узле, вы можете быть в состоянии чтобы увидеть это более четко, то, что вы видите, является представлением по умолчанию, используемым для всех объектов Python, тип которых не определяет или не наследует __repr__).
Таким образом, замена случайного поддерева между двумя разными деревьями требует только тщательного обновления всех избыточных частей информации, которые вы храните (и это должно ВСЕ быть в синхронизации).Кстати, было бы проще, если бы такие обновления были методами Tree и/или Node и поэтому использовались для любого из различных видов «редактирования» (вставки, удаления и т. Д.), А не были глубоко погружены в функцию, которая выполняет обновления как часть случайного обмена - это хорошая практика OO. Но это несколько проблема.
Вы также не говорите нам точно, как работает атрибут branch, я предполагаю, что это строка, «слева» или «справа» (если нет родителя, т. Е. Корневого узла).
Чтобы удалить поддерево, вам необходимо обновить: родительский узел, установив на None свой соответствующий атрибут; корень поддерева, установив None в его родительские и ветвящиеся атрибуты; И Дерево, удалив эту запись из атрибута дерева thedict. Вам также нужно будет запомнить, что такое родительский элемент и ветвь, чтобы иметь возможность вставить в это место другое поддерево. Поэтому ...:
def removeSubtreeFromTree(tree, keyindict):
subtreenode = tree.thedict.pop(keyindict)
parent, branch = subtreenode.parent, subtreenode.branch
# a sanity chech can't hurt...;-)
assert getattr(parent, branch) is subtreenode
subtreenode.parent, subtreenode.branch = None, None
setattr(parent, branch, None)
return subtreenode, parent, branch
Теперь, чтобы добавить новое поддерево к данному родителю и ветви в дереве проще:
def addNewSubtree(tree, subtreenode, parent, branch):
# sanity checks R us
assert getattr(parent, branch) is None
assert subtreenode.parent is None
assert subtreenode.branch is None
setattr(parent, branch, subtreenode)
subtreenode.parent = parent
subtreenode.branch = branch
tree.thedict[tree.nextkey] = subtreenode
tree.nextkey += 1
Примечание Вы не можете просто повторно использовать предыдущие ключи: там может быть «конфликтом» (предполагая, что ключи уникальны только в пределах одного заданного дерева ... если вы сделали их глобально уникальными, то вы действительно могли бы их повторно использовать).
И, наконец, можно выполнить эти две операции и немного больше вместе. Если вам никогда не нужно «обменивать» корень дерева, он проще (никакого специального случая, необходимого для работы с поддеревом без родителя ...), поэтому я временно предполагаю, что (если вы хотите больше общности, вам нужно будет кодировать в привередливые особых случаях - в идеале после рефакторинга вещи, чтобы быть методы, как я ранее предложил; -) ...:
def randomNonrootSubtree(tree):
# we're in trouble if the tree ONLY has a root w/no really SUB trees;-)
assert len(tree.thedict) > 1
while True:
thekey = random.choice(tree.thedict.keys())
subtree = tree.thedict[thekey]
if subtree.parent: return thekey
и наконец ...:
def theSwapper(t1, t2):
k1 = randomNonrootSubtree(t1)
k2 = randomNonrootSubtree(t2)
st1, p1, b1 = removeSubtreeFromTree(t1, k1)
st2, p2, b2 = removeSubtreeFromTree(t2, k2)
addNewSubtree(t1, st2, p1, b1)
addNewSubtree(t2, st1, p2, b2)
Обратите внимание, что это, в отличие от Алекса , предполагает, что ни один из узлов не является корнем его дерева. – Anon
(Чтобы справиться с этой возможностью, вы могли бы добавить случаи elif к родительским обновлениям, поэтому elses не поймают «правильные» и корневые случаи. – Anon