Удалить из BST не удаляя узел - PullRequest
Новая
       11

Удалить из BST не удаляя узел

0 голосов
/ 11 ноября 2018

Это вопрос к собеседованию по удалению узлов из BST.

Что-то не работает, как ожидалось, когда я попытался установить node = node.right в строке 31. Я обнаружил, что это не работает должным образом, поэтому мне пришлось вручную установить node.value, node.right, node. оставил на node.right. * ... который работал. Тем не менее, сейчас я занимаюсь удалением листа (строка 36), я попытался установить узел = Ни один не работал по тем же причинам, на которые я рассчитывал. Я также попробовал del node, который тоже не работает.

Почему это не работает так, как ожидалось? Я проследил код через отладчик, переменная узла имеет тот же адрес памяти, что и основное дерево. Это какая-то проблема объема? Я не понимаю; спасибо за помощь.

Копирование полного кода ниже с небольшим примером: 

class Tree(object):
  def __init__(self, x):
    self.value = x
    self.left = None
    self.right = None
def deleteFromBST(t, queries):
    def find(t, q):
        if not t:
            return None
        if t.value == q:
            return t
        if t.value > q:
            return find(t.left, q)
        else:
            return find(t.right, q)

    def delete(t, q):
        n = find(t, q)
        if n:
            if n.left:
                rp = n
                r = n.left
                while r.right:
                    rp = r
                    r = r.right
                n.value = r.value
                rp.right = None

            elif n.right:
                # n = n.right
                n.value=n.right.value
                n.left=n.right.left
                n.right=n.right.right
            else:
                # n = None
                del n

    for q in queries:
        delete(t, q)
    return t

tree_dic={
    "value": 5,
    "left": {
        "value": 2,
        "left": {
            "value": 1,
            "left": None,
            "right": None
        },
        "right": {
            "value": 3,
            "left": None,
            "right": None
        }
    },
    "right": {
        "value": 6,
        "left": None,
        "right": {
            "value": 8,
            "left": {
                "value": 7,
                "left": None,
                "right": None
            },
            "right": None
        }
    }
}
queries=[4, 5, 6,7]
# t=Tree(tt['value'])
def build_tree(d):
    r=Tree(d['value'])
    if d['left']:
        r.left=build_tree(d['left'])
    if d['right']:
        r.right=build_tree(d['right'])
    return r
t=build_tree(tree_dic)
o=deleteFromBST(t,queries)
print('hi')
...