Удаление значения из двоичного дерева поиска

Question

Удаление значения из двоичного дерева поиска

Я пишу функцию, которая удалит запись из двоичного дерева поиска, с которым связан данный ключ. Пока у меня есть это для моего кода:

template <typename Item, typename Key = Item>
bool BSTree<Item,Key>::remove(const Key& key) {
bool removed = false;
Node* ptr = root;
if(ptr == NULL)
return removed;
while(key != ptr) {
if(ptr == NULL)
return removed;
else if(key > ptr)
ptr = ptr->right();
else
ptr = ptr->left();
}
removed = true;
Item max = max(ptr);
ptr->data() = max;
Node* prev = ptr;
while (ptr != NULL) {
prev = ptr;
ptr = ptr->right();
}
delete ptr;
if (prev->left() != NULL)
prev = copy(prev->left());
delete prev;
return removed;
}

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

У меня также есть проблема с последними тремя строками функции. В каждом из них «if», «delete» и «return» подчеркнуты и дают мне ошибку «Ошибка: ожидалось объявление». Я понятия не имею, что происходит с этим, и буду очень признателен за обратную связь!

1

binary-search-tree binary-tree c++pointers

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

ИМХО, я вижу пару вещей.

Для удаления BST вам нужен лучший метод трансплантации, кроме вашей «копии», по крайней мере, вы должны найти следующий наименьший узел по сравнению с тем, который будет удален.
ptr-> data () = max; Я предполагаю, что ваш метод data () возвращает ссылку на член в Item. Не так, просто чувствует себя странно.
У вас есть два оператора «delete», но разве вы не должны удалять только один элемент?
В этой секции:
```
while (ptr != NULL) {

prev = ptr;
ptr = ptr->right();
}
delete ptr;
```
После выхода из while значение ptr равно NULL, поэтому вы удаляете NULL, а не круто.

0