Здравствуйте, LaptevVV, Вы писали:

LVV>Понятно. Эльконина — к ответу!
LVV>До чего дошло: студент делал курсовую по операциям двоичного дерева и НЕ ПРОЧИТАЛ ни одного учебника.
LVV>И даже в инете — НЕ читал!
LVV>ибо удаление узла сделал как ему в голову пришло, а не как положено...

Кстати, данный пример хорошь тем, чтобы разобрать его и понять состав и запах продуктов работы организмов, которые оставляют нам предыдущие поколения. Случай тут кстати практически классический:
Возьмем конкретно формулировку алгоритма удаления ноды с 2мя чилдами из википедии:

Если оба ребёнка присутствуют, то
1. Если левый узел m правого поддерева отсутствует (n->right->left)
Копируем из (8) в (4) поля K, V и ссылку на правый узел.
Иначе
2. возьмем самый левый узел m, правого поддерева n->right;
скопируем данные (кроме ссылок на дочерние элементы) из m в n;
рекурсивно удалим узел m.

Во-первых о формулировке: прочитав ЭТО нужно либо рисовать на бумаге, либо напрячь воображение, чтобы представить чего тут закодировано. Ну ОК — представил. И с удивлением обнаружил, что и пункт 1 и пункт 2 описывают по сути один и тот-же юз кейз. Собственно то, что мне первым и пришло в голову — надо найти ближайшее большее или меньшее число, чем удаляемое и поместить его на место удаляемого. Эти два нода (ближайшие большее и меньшее) единственные в дереве, которые не сломают сортировку дерева при переносе одного из них место удаляемого нода. Затем перенеснный нод надо удалить. Все! — это и есть то-же, что делает описанный алгоритм, который зачем-то разбили на 2 ветви. Скажете разбили потому, что в п. 2 есть рекурсия для удаления m? Но дело в том, что она там вовсе не нужна! Вместо рекурсии нужно вызвать метод, который умеет удалять нод с одним чилдом или без детей — у нода m точно нет левого чилда — иначе бы он не был самым левым. Значит проверка на наличие 2х чилдов у данного нода лишняя и значит никакой рекурсии не нужно — она просто просадит производительность.
Скажете не повезло с примером? Ну я очень часто сталкиваюсь с неэффективными решениями, которые выдаются за классические. Почти всегда дорабатываешь напильником. После обточки часто обнаруживаешь решение, которое ты уже давно знаешь. Так что на вашем месте я бы наследством предков сильно не размахивал бы. Прочитать статью желательно конечно, но конкретно в данном случае я бы только потерял время. Написанное с ходу решение будет эффективнее.

Здравствуйте, LaptevVV, Вы писали:

LVV>Понятно. Эльконина — к ответу!
LVV>До чего дошло: студент делал курсовую по операциям двоичного дерева и НЕ ПРОЧИТАЛ ни одного учебника.
LVV>И даже в инете — НЕ читал!
LVV>ибо удаление узла сделал как ему в голову пришло, а не как положено...

Кстати, данный пример хорошь тем, чтобы разобрать его и понять состав и запах продуктов жизнедеятельности, прелставителей предыдущих поколений. Случай тут кстати практически классический:
Возьмем конкретно формулировку алгоритма удаления ноды с 2мя чилдами из википедии:

Если оба ребёнка присутствуют, то
1. Если левый узел m правого поддерева отсутствует (n->right->left)
Копируем из (8) в (4) поля K, V и ссылку на правый узел.
Иначе
2. возьмем самый левый узел m, правого поддерева n->right;
скопируем данные (кроме ссылок на дочерние элементы) из m в n;
рекурсивно удалим узел m.

Во-первых о формулировке: прочитав ЭТО нужно либо рисовать на бумаге, либо напрячь воображение, чтобы представить чего тут закодировано. Ну ОК — представил. И с удивлением обнаружил, что и пункт 1 и пункт 2 описывают по сути один и тот-же юз кейз. Собственно то, что мне первым и пришло в голову — надо найти ближайшее большее или меньшее число, чем удаляемое и поместить его на место удаляемого. Эти два нода (ближайшие большее и меньшее) единственные в дереве, которые не сломают сортировку дерева при переносе одного из них место удаляемого нода. Затем перенеснный нод надо удалить. Все! — это и есть то-же, что делает описанный алгоритм, который зачем-то разбили на 2 ветви. Скажете разбили потому, что в п. 2 есть рекурсия для удаления m? Но дело в том, что она там вовсе не нужна! Вместо рекурсии нужно вызвать метод, который умеет удалять нод с одним чилдом или без детей — у нода m точно нет левого чилда — иначе бы он не был самым левым. Значит проверка на наличие 2х чилдов у данного нода лишняя и значит никакой рекурсии не нужно — она просто просадит производительность.
Скажете не повезло с примером? Ну я очень часто сталкиваюсь с неэффективными решениями, которые выдаются за классические. Почти всегда дорабатываешь напильником. После обточки часто обнаруживаешь решение, которое ты уже давно знаешь. Так что на вашем месте я бы наследством предков сильно не размахивал бы. Прочитать статью желательно конечно, но конкретно в данном случае я бы только потерял время. Написанное с ходу решение будет эффективнее.