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

Что еще добавить? какие проверки? и как удалить узел с двумя потомками?Нужно вводить новый указатель *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 быстрая сортировка на основе рекурсии

Ладно, раз уж пошел такой жесткий оффтоп, и наш "уважаемый" HellStranger все никак не успокоится...



При flat модели памяти, код и данные используют одно и то же адресное пространство. Так что, не говори о том чего не знаешь.




По умолчанию компилятор сделал бы в данном случае, примере что я указал, RETN. Но для вас это сложно, я понимаю.



Про развертку стека почитайте. Стек в процессорах семейства Intel поддерживается на аппаратном уровне. Уже говорилось, что QuickSort реализована "разверткой" рекурсии. И делается это для того, чтобы скомпилированный код был компактен, так как со стеком проще работать, и не плодить немыслимое количество условных переходов.

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

Предлагаю вам реализовать вышеописанный алгоритм на циклах, вот и сравним, у кого код меньше и быстрее...

Это сообщение отредактировал(а) niteo - 31.7.2010, 16:13

Это всё очень сильно зависит от конкретной реализации конктретного алгоритма.  Вообще речь шла о сложности алгоритма в плане выполнения операций алгоритма, а не дополнительных операций вызова функций, доступа к структурам данных и т.д. С этой точки зрения разницы в рекурсивном и нерекурсивном алгоритмах просто нет! Это доказывает и пример с qsort, отправляю к Вирту "Алгоритмы и структуры данных", разница микроскопическая, и я уже объяснял откуда она берётся... Как раз в дополнительных операциях доступа к стэку и т.д...

Доказательство полной некомпетентности- утверждение "По умолчанию компилятор сделал бы в данном случае". Каждый производитель компиляторов возврат из функий оптимизирует по своему! Вы много дизасэмблированного различными компиляторами кода видели?.. Про модель памяти flat мне тоже заливать не надо, далеко не везде используется эта модель памяти.



Стек для процессора- эта такая же область памяти, как и все остальные! Это не какой-то отдельный жёстко зашитый адресный диапазон, работа с которым как-то жутко ускорена! То, что вы в архитектуре абсолютно ни черта не понимаете, это сразу бросается в глаза. Так что не умничайте впредь! Если говорите что-то почитать, то давайте хотя-бы автора, названия книги от вас не дождёшься, это ясно...



По поводу реализации я уже объяснил, что вряд-ли кто-то будет тратить своё время не реализацию алгоритма. Меряться письками на интерес, мне за это не платят на работе! А будет проект по данной тематике- специально выложу код! Я здесь много раз помощи просил чисто даже в плане документации или разъяснения (код не просил никогда!), и на мои вопросы ДО СИХ ПОР НЕ БЫЛО НИ ОДНОГО ОТВЕТА! Так что заглохни со своей критикой, а читай книжки!

Обращаясь к HellStranger... Ну вот что ты за человек, ты же в последнем своем коменте просто "слился". Неужто ты этого не понимаешь? Программист мля... 

Да вот как раз программист "мля" это ты, который горазд писать псевдокод на форумах.  Нормальный программист, как мне кажется, к любому проекту, даже функции на 20 строк должен подходить серьёзно: со всевозмножной оптимизацией этих 20 строк. Париться над этим, чтобы какому-то программисту-любителю что-то доказать, мне влом; а писать как ты ###код на коленках за 15 минут... Не наш метод... Так что большой вопрос, кто из нас слился.  Ещё раз говорю, будет производственная необходисомть по схожей тематике, без проблем выложу наромальный код, а не псевдоискусство, сливальщик ты наш... 

HellStranger, ты меня к Вирту отправил? 

Да. Алгоритны и структуры данных. Второе издание. Тебе ещё страницу сказать, где результаты сравнения указаны?..