#python #data-structures
Вопрос:
Я внедряю BST, и все работает, даже удаление с двумя детьми.Единственная ошибка заключается в удалении листа, что кажется такой тривиальной задачей. Кажется, все еще есть ссылка на конечный узел, но я не могу разобраться в этой проблеме.Установка node = None не удаляет весь узел.Я также попробовал del node, но безуспешно.Если бы вы могли определить проблему, было бы неплохо.
import random class Node: def __init__(self, data): self.data = data self.left = None self.right = None self.parent = None self.left_child = None self.right_child = None self.level = None class Tree: def __init__(self): self.root = None self.size = 0 self.height = 0 def _insertion(self, root, data): new_node = Node(data) if root.data lt; data: if root.right: return self._insertion(root.right, data) root.right = new_node root.right.parent = root root.right_child = root.right return if root.data gt; data: if root.left: return self._insertion(root.left, data) root.left = new_node root.left.parent = root root.left_child = root.left return def insertion(self, data): new_node = Node(data) if not self.root: self.root = new_node return return self._insertion(self.root, data) def _get_height(self, root): if not root: return -1 left_height = self._get_height(root.left) right_height = self._get_height(root.right) return 1 max(left_height, right_height) def get_height(self): if not self.root: return 0 return self._get_height(self.root) def fill_random(self, num_nodes): for i in range(num_nodes): random_num = int(random.random()*100) self.insertion(random_num) def _inorder(self, root): if root: self._inorder(root.left) print(root.data) self._inorder(root.right) def inorder(self): root = self.root return self._inorder(root) def get_max(self, node): while node.right: node = node.right return node.data def search(self, data): root = self.root while root.right or root.left: if root.data lt; data: root = root.right if root.data gt; data: root = root.right if root.data == data: return root return None def _delete_node(self, root, data): if root: if root.data lt; data: return self._delete_node(root.right, data) if root.data gt; data: return self._delete_node(root.left, data) if root.data == data: if not root.left and not root.right: root = None return if not root.left and root.right: root = root.right root.right = None return if not root.right and root.left: root = root.left root.left = None return if root.right and root.left: value = self.get_max(root) print(f"This is the value: {value}") root.data = value self._delete_node(root.right, value) def delete_node(self, data): if not self.root: return None return self._delete_node(self.root, data) if __name__ == '__main__': my_tree = Tree() my_tree.insertion(33) my_tree.insertion(36) my_tree.insertion(25) my_tree.insertion(20) my_tree.insertion(27) my_tree.insertion(35) my_tree.insertion(39) my_tree.delete_node(33) my_tree.inorder() my_tree.search(35) Комментарии:
1. Отредактируйте вопрос, чтобы объяснить: Как вы замечаете проблему? Что происходит, что должно произойти?
Ответ №1:
В вашей _delete_node функции это не помогает установить root значение None . Это влияет только на переменную, но не вносит никаких изменений в дерево.
Распространенный «трюк» состоит в том, чтобы вернуться root к вызывающему абоненту, который затем отвечает за присвоение возвращаемого значения тому месту, где на него есть ссылка в дереве. Например, если рекурсивный вызов был выполнен с root.left аргументом as, и рекурсивный вызов хочет удалить этот узел, он вернется None , и вызывающий должен затем назначить (все, что он получит обратно) root.left . Так что теперь дерево мутировало, как и было задумано.
Вот ваши delete_node функции, адаптированные в соответствии с этим принципом:
def _delete_node(self, root, data): if root: if root.data lt; data: root.right = self._delete_node(root.right, data) elif root.data gt; data: root.left = self._delete_node(root.left, data) elif not root.left: return root.right elif not root.right: return root.left else: value = self.get_max(root) print(f"This is the value: {value}") root.data = value root.right = self._delete_node(root.right, value) return root def delete_node(self, data): if self.root: self.root = self._delete_node(self.root, data) Еще одно замечание
У вашей search функции есть некоторые проблемы:
whileУсловие должно проверить, есть лиrootNoneоно, прежде чем обращаться к любому из его атрибутов.ifБлоки должны быть связаны друг сelifдругом , иначе выполнение может попасть во второйifблок, который не является намерением.
Вот исправленная версия:
def search(self, data): root = self.root while root: if root.data lt; data: root = root.right elif root.data gt; data: root = root.left else: return root return None Небольшое улучшение
Чтобы помочь отладить этот код, я inorder немного изменил метод, чтобы дерево печаталось с отступами:
def _inorder(self, root, indent=""): if root: self._inorder(root.left, indent " ") print(indent str(root.data)) self._inorder(root.right, indent " ") Это помогает быстро увидеть структуру дерева. Возможно, вы даже захотите переключиться влево и вправо, чтобы это выглядело как повернутое дерево.
Комментарии:
1. действительно хороший ответ
2. только один вопрос: в операторе else функции удаления, как вы можете установить root.right для функции удаления. Допустим, мы удалим корень. Затем мы находим максимальное значение, копируем значение максимального значения в корень. Затем мы вызываем функцию удаления, которая не вернет ничего, так как это конечный узел(не имеет ни правого, ни левого).. Как мы можем установить self.root.right = Нет
3. Это именно то, что произойдет на узле, который является родителем этого конечного узла. На этом родительском узле мы выполняем рекурсивный вызов, который вернется
None, и поэтому этот вызывающий абонент назначит это возвращаемое значение (None)root.right(«корень» — это родительский узел листа).4. Извините, но я не могу понять, как из корневого узла мы можем рекурсивно перейти к родительскому узлу конечного узла, установить право, равное Нулю, а затем установить родителя листа справа от корня. Я, наверное, тупой, но все равно не понимаю 😉
5. да, теперь я наконец понял это, мне нужно было нарисовать все дерево и записать каждый рекурсивный шаг и посмотреть, что возвращает каждый шаг. Большое тебе спасибо, тринко, хорошего дня и всей оставшейся жизни 🙂
Ответ №2:
Этот блок кода ничего не делает:
if root.data == data: if not root.left and not root.right: root = None return потому root что это локальная переменная; переназначение ее на None не влияет на дерево.
Что вам нужно сделать, так это изменить указатель или родительского right узла left . Я бы предложил сделать это до рекурсии, но вы также можете решить эту проблему, передав родительский узел в эту функцию.
Комментарии:
1. Сэм, не мог бы ты взглянуть на решение тринко. Я все понимаю, но я не понимаю root.right = self._delete_node(root.right, значение)
2. Сделав это, я доберусь до узла, который хочу удалить
3. Но почему я устанавливаю его на корневой.правильно. Таким образом, как только deletenode вернет значение None, для root.right будет установлено значение None. Что я упускаю? Извините, что спрашиваю вас, но я не могу понять, почему эта штука работает.