C ++ удалить узел двоичного дерева поиска

Question

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

bool BinSTree::remove_root(treeNode*& node) {
   if(node -> left == NULL && node -> right == NULL) {


   }
   elseif(node -> left != NULL && node -> right != NULL) {


   }  
   else {

   }                           

}

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

Answer 1

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

Удаление из дерева - интересный случай, и я помню, как ломал голову над ним, когда писал свою собственную реализацию дерева AVL в C в конце 80-х.

Answer 2

Когда вы удаляете узел,
- Если это лист, вы сделали.
- Если у него есть один ребенок, продвиньте его, а затем удалите ребенка из его поддерева (позвонив себе).
- Если у него двое детей, выберите, какого из них продвигать, а затем удалите этого ребенка из его поддерева (позвонив себе).

Иногда, кого из двух детей вы выбираете, зависит от таких факторов, как
- корень поддерева - это наименьший из всех узлов в поддереве
- корень поддерева - больше всего узлов в поддереве
- некоторая окраска или другое побочное состояние должно быть сохранено

Это должно отвлечь вас от центра.

Answer 3

В дополнение к другим ответам (и предполагая, что это домашняя работа, смысл которой нужно учиться), вы можете найти «Алгоритмы + структуры данных = программы» Никлауса Вирта, очень полезные как в целом, так и дляВаша конкретная проблема.

Это классическая маленькая книга, драгоценный камень.

Надеюсь, она будет доступна в вашей ближайшей (университетской) библиотеке?

Приветствия и hth.,

Answer 4

Эта вики-страница в бинарном дереве поиска может помочь.

Answer 5

Для начала, в вашей функции также должен быть параметр для родителя (если ваше дерево не имеет указателей на родителей, что, как кажется, не имеет).

С этим изменением вам будет легче понять все остальное. Но то, как вы вызываете эту функцию, становится важным.

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

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