Как удалить поддерево в питоне - PullRequest
Новая
       25

Как удалить поддерево в питоне

1 голос
/ 28 августа 2011

Я (все еще) имею дело с древовидной структурой в программе на Python. У каждого узла в дереве есть словарь "children", ключи которого содержат информацию о дуге и значения являются дочерними узлами. (И каждый узел имеет пару (parent, parent_arc), где parent - это родительский узел, а parent_arc - дуга, по которой родительский узел связывает этот узел.)

Теперь я хочу удалить поддерево, корнем которого является дочерний элемент узла N. Скажем, дочерний элемент - N.children [a].

del N.children [a] просто не освободит память, занятую поддеревом. Должен ли я реализовать метод для удаления каждого узла в поддереве? Как я могу это сделать ? Нужно ли переопределять класс узла для эффективного сокращения поддерева?

Спасибо!

1 Ответ

2 голосов
/ 28 августа 2011

Когда A -> B и B -> A, у вас есть эталонные циклы. Хороший способ обойти это - заставить детей использовать слабые ссылки, чтобы указать на родителя. Примерно так: 

import weakref
class Node():
    parent = None
    child = None
    @property
    def parent(self):
        parent = self._parent()
        if parent is not None:
            return parent
        raise ValueError("parent has been deleted")
    @parent.setter     # python 2.6+
    def parent(self, parent):
        self._parent = weakref.ref(parent)

Теперь у узла нет прямой ссылки на его родительский элемент, и когда вы удаляете дочерний элемент, он действительно исчезает *. (Вам может понадобиться использовать тот же метод для parent_arc.)

* Обратите внимание, что даже если Python освободит объекты быстрее, если не существует циклов ссылок, он может не вернуть эту память обратно ОС.

...