Добрый День.Пишу бинарное дерево.Возникла проблема с правильным удалением узла.
Вот мой алгоритм:

Что еще добавить? какие проверки? и как удалить узел с двумя потомками?Нужно вводить новый указатель *parent или можно обойтись без него?

Тебе надо делать рекурсивный алгоритм. В цикле это глупо. ИМХО

Вот почитай: Бинарное дерево

Удаление одного узла из бинарного дерева без поддеревьев этого узла- это в чистом виде memory leaks, чтобы предотвратить "течку", алгоритм должен быть рекурсивным, удаляющим и поддеревья данного узла. У тебя я этого, пусть и не особо изучав твой алгоритм, не увидел... Как ты собираешься сохранить бинарность своего дерева, если удаляемый узел имеет в точности 2 поддерева, тоже не совсем понятно. А алгоритм, удаляющий только крайние узлы и узлы, имеющие одно поддерево, непонятно зачем нужен...

Добавлено через 4 минуты и 41 секунду

А у него и цикла нету собственно... Цикл только для пробега по дереву и поиска удаляемого узла.  Делать и поиск узла рекурсивным- не совсем айс, так как цикл быстрее и экономнее рекурсии. 

Есть дерево 
     11
  7       9 
        8     10
Как удалить вы говорите число 9 циклом? чтобы на него место стало 10.
         11
   7         10
           8

Рекурсия проще раз в 10. посматрите реализацию рекурсивного алгоритма пробегания по дереву. там 3 строчки. И все таки я советую EgorTheBlade сходить по ссылочке, которую я дал. Там расписано все на "пальцах"

Проще реализуется и проще работает, разные понятия... Рекурсивные обходы деревье рассказываются на младших курсах университетов, так что нового вы мало что открыли. Циклический алгоритм потребует куда меньше ресурсов (тот же стек), нежели рекурсивный. Но суть не в этом. Он не удаляет поддеревья... Хотя, как я понял, задача у него не совсем в удалении. В любом случае, алгоритм неверный, потому что он не обрабатывает поддеревья. А EgorTheBlade я бы посоветовал шевелить мозгой дальше. Это куда как приятнее, чем хватать готовые решения из гугла, а составлять алгоритм за вас вряд-ли кто-то станет...

Не говорите глупостей, уважаемый.  При рекурсии передается указатель на узел дерева и адрес возврата 4 + 4 байта. Итого 8 байт в стек. Скорость выполнения RET и JMP одинаковая. При чем в вашем случае, с циклом приходится инициализировать туеву кучу переменных, не считая того что код получается вообще нечитаемым и огромным.

Как я и писал, вот алгоритм из ссылки:



А вот его реализация, могут быть ошибки, но как то так, сходу написал его:

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

Уважаемый, ахинея которую вы несёте, доказывает, что понимания основ элементарных вещей у вас отсутсвует напрочь! Во-первых, скорость выполнения инструкций RET и JMP совершенно не одинаковая в различных случаях. JMP осуществляет только ближние переходы в рамках данного семгмента, RET- любые переходы. И что случится в случае, если очередной предсказанный переход (читай архитектуру IA32/64 или Ассемблер Юрова) окажется неверным? Накинется пара сотен лишних тактов. Так что говорить о скорости выполнения инструкций перехода- дело вообще не благодарное. Почитайте внимательнее документацию! Да и речь собственно о другом! Локальные переменные, которые Вы объявляете и используете при каждом рекурсивном вызове где по-вашему храниться будут?.. Симстема их в уме держать будет?    Так что Ваша арифметика 4+4 на уровне 5-го класса средней школы!

HellStranger на удивление прав

только про переходы внутри сегмента - это не применимо к x86-32

Это сообщение отредактировал(а) Abyx - 30.7.2010, 18:06

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

псевдокод:

для двусвязного дерева надо добавить откаты назад

Уважаемый, вам туда же, куда и предыдущему оратору: официальный мануал Intel IA32/64 либо, на обычном русском языке Юров. Как раз в отношении других архитектур это, может быть, и не применимо, а сегментностраничную организацию памяти архитектуры Intel ещё никто не отменял.

Добавлено через 1 минуту и 45 секунд


А как при этом стек экономится...  Да и лишних CALL и RET нет.

нам читать лень, мы просто знаем 
при "плоской" (flat) модели адресации основные сегменты (cs, ds, es) никакой роли не играют, их можно игнорировать.


пишите "jmp near" и "retn"



зато O(f(n)) сложность другая.

Да уж... CS игнорируется... Откуда ж тогда код брать?..  Ну да ладно, тебе хоть сцы в глаза, скажешь божья роса, раз для тебя официальный док Intel это старый завет. 




Ты видел какие команды указал предыдущий оратор?.. О спецификаторе near и речи не было. Да и смысл его указывать у JMP. В соседний сегмент всё-равно не перепрыгнешь! 




Не совсем понятно за счёт чего сложность другая?.. Просматриваться будут всё-равно всё узлы последовательно, это вам не сортировка... Кстати, немного отвлечёмся от темы, результаты сравнения qsort рекурсивной и нерекурсивной пактически одинаковы, нерекурсивный вариант уступает самый мизер из-за использования стека и обращения к нему... Это отступление к тому, что при одном и том же алгоритме на его сложность совершенно не влияет наличие либо отсутствие рекурсии... Так что опять вы блеснули непонятно чем...

сильно platform-dependend. есть личный старинный опыт, когда стандартную быструю сортировку применять было крайне неэффективно из-за больших накладных расходов на вызов функции сравнения: программа компилировалась в шитый код, достаточно шустрый, но с определенными тонкостями в производительности. в результате была написана быстрая сортировка на основе цикла (что бы избежать вызовов функций). так эта сортировка в виде шитого кода работала на порядок быстрее, чем стандартная из dll.
но это лирика, для компилируемого языка не должно быть принципиальных отличий в реальной работе между нормально реализованными рекурсивной и нерекурсивной версией, что бы из-за этого жертвовать удобством и скоростью разработки. кажется, в STL быстрая сортировка на основе рекурсии