DrRacket Удаление корня бинарного дерева поиска - PullRequest
Новая
       15

DrRacket Удаление корня бинарного дерева поиска

1 голос
/ 12 ноября 2011

ОБРАТИТЕ ВНИМАНИЕ, ЧТО ЭТО РАБОТАЕТ! -> Я не ищу прямых примеров кода, а скорее слегка массирую мои рассуждения ...

Меня попросили написать функцию, которая удаляет корень двоичного дерева поиска, выполняя три вещи: я) вращение дерева вправо II) удаление корня правого поддерева (который был первоначальным корнем BST) iii) восстановление bst с новым корнем (который был слева от исходного дерева) и соответствующими перестановками дочерних элементов этого узла ... Вот что у меня есть: 

    (define (rm-root my-bst)
      (list (key (rot-r my-bst)) 
            (left (rot-r my-bst)) 
            (append (right (right (rot-r my-bst))) 
                    (left (right (rot-r my-bst))))))

Что здорово, ожидайте, что оно не перестраивает дерево с дочерними элементами узла, который был "продвинут" до корневого узла. Может ли кто-нибудь помочь мне подумать о том, как мне следует реализовать это? Я должен упомянуть, что мы определили Bst's как списки и что функция rot-r вращает bst вправо. Спасибо.

1 Ответ

1 голос
/ 23 ноября 2011

Ну, я не уверен, что это будет полезно через 12 дней после того, как вопрос был задан, но здесь идет.

Чтобы было ясно, я предполагаю, что структура данных имеет форму (ключ списка слева направо), где слева и справа также деревья (или пустые, но это не имеет значения) Если это не так, потребуется разъяснение этого.

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

Я бы проверил реализацию rot-r на вашем месте, так как это, по-видимому, основная возможность того, что что-то пойдет не так.

...