Удалить в BST - PullRequest
Новая
       17

Удалить в BST

0 голосов
/ 30 мая 2018

Мне было интересно, почему мой метод удаления для моего BST не работает.Я реализовал рекурсию, и по какой-то причине ни один узел не удаляется. 

def delete(self,node, val):
    if(node == None):
        return None
    if(val < node.data):
        node.left =  self.delete(node.left,val)
    elif( val > node.data):
        node.right = self.delete(node.right,val)
    else:
        if(node.right ==None and node.left ==None):
            return None

        elif(node.left==None): # delete the node holding 1 child
            node=node.right

            return node

        elif(node.right==None):
            node = node.left
            return node
        elif(node.right and node.left):
            delete = node.right
            while(delete.left):
                delete = delete.left
            node.data = delete.data
            node.right = delete(node.right,delete.data)
    return node


    testTree.delete(testTree.root,30)
    testTree.printInorder(testTree.root)

Может быть, я не удаляю напрямую?

1 Ответ

0 голосов
/ 30 мая 2018

Вы написали node = node.right, но вы действительно хотите return node.right (и аналогично для левого регистра).

Поскольку левый или правый потомок родителя будет затем установлен на возвращаемое значение,больше не должно быть ссылок на текущий узел, и он будет собирать мусор.

Точно так же, когда node не имеет дочерних элементов, вы делаете del(node) (кстати, скобки не нужны), что просто делаетnode неопределенное имя.Вместо этого вы должны сделать return None, чтобы левый или правый дочерний элемент родительского элемента был установлен на None, и тогда узел будет собирать мусор из-за отсутствия ссылок.

В случае, когда узел должен бытьУдаленный имеет двух дочерних элементов, вы устанавливаете node.data = delete.left, который предположительно присваивает узлу что-то, что должно быть целочисленным.Вы, вероятно, хотите node.data = delete.data.

Более того, вы, вероятно, не хотите просто делать del(node.right).Все, что нужно сделать, это удалить атрибут right из node.Вы должны отслеживать родителя delete и удалять его как дочернего от этого родителя.

Другая проблема заключается в том, что у delete есть дети.В общем и целом, существует ряд проблем, поэтому это может быть любой из них.

Редактировать: Чтобы обратиться к самой последней версии кода, случай с двумя детьми может быть выполнен примерно так: 

swap_node = node.right
parent = node

# Find the leftmost child of the right subtree and its parent
while swap_node.left:
    parent = swap_node
    swap_node = swap_node.left

node.data = swap_node.data
# The next line works whether or not swap_node has a right child
parent.left = swap_node.right
return node

Это перемещает данные от самого левого дочернего элемента правого поддерева к текущему узлу и удаляет этот узел из его дерева.Вам не нужен рекурсивный вызов для удаления, потому что вы уже знаете, где находится узел и что у него нет левого потомка.

...