Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Удаление узла из дерева

Автор: EgorTheBlade 30.7.2010, 11:01

Добрый День.Пишу бинарное дерево.Возникла проблема с правильным удалением узла. Вот мой алгоритм: Код template<class T> void Tree<T>::Del(const T &key) {     Node<T> *temp,*check,*max;     check = root;     temp = root;     while(check != NULL)     {         temp = check;         if(check->info == key){std::cout<<"found and deleted\n";break;}         if(key < check->info)check = check->left;         else check = check->right;     }     // if(check == NULL){std::cout<<"elem not found";return;}     if((check->left == NULL) && (check->right == NULL))// if elem haven't childs;     {         if(check == temp)         {             std::cout<<"Del Trace";             delete(check);             root->left = NULL;             return;         }         if(temp->left == check) // if elem left;             temp->left = NULL;         else             temp->right = NULL;         delete(temp);         return;     }     if(check->left == NULL)// if only right child;     {         if(check == temp)         {             check = check->right;             delete(check);             return;         }         if(temp->left == check)// if elem is left;             temp->left = check->right;         else                       temp->right = check->right;         delete (check);         return;     } } Что еще добавить? какие проверки? и как удалить узел с двумя потомками?Нужно вводить новый указатель *parent или можно обойтись без него?

Автор: niteo 30.7.2010, 11:36

Тебе надо делать рекурсивный алгоритм. В цикле это глупо. ИМХО Вот почитай: http://traditio.ru/wiki/Бинарное_дерево

Автор: HellStranger 30.7.2010, 11:44

Удаление одного узла из бинарного дерева без поддеревьев этого узла- это в чистом виде memory leaks, чтобы предотвратить "течку", алгоритм должен быть рекурсивным, удаляющим и поддеревья данного узла. У тебя я этого, пусть и не особо изучав твой алгоритм, не увидел... Как ты собираешься сохранить бинарность своего дерева, если удаляемый узел имеет в точности 2 поддерева, тоже не совсем понятно. А алгоритм, удаляющий только крайние узлы и узлы, имеющие одно поддерево, непонятно зачем нужен... Добавлено через 4 минуты и 41 секунду Цитата(niteo @ 30.7.2010,  11:36) Тебе надо делать рекурсивный алгоритм. В цикле это глупо. ИМХО Вот почитай: http://traditio.ru/wiki/Бинарное_дерево А у него и цикла нету собственно... Цикл только для пробега по дереву и поиска удаляемого узла.  Делать и поиск узла рекурсивным- не совсем айс, так как цикл быстрее и экономнее рекурсии.

Автор: EgorTheBlade 30.7.2010, 12:35

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

Автор: niteo 30.7.2010, 12:42

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

Автор: HellStranger 30.7.2010, 12:55

Цитата(niteo @  30.7.2010,  12:42 ) Рекурсия проще раз в 10. посматрите реализацию рекурсивного алгоритма пробегания по дереву. там 3 строчки. И все таки я советую EgorTheBlade сходить по ссылочке, которую я дал. Там расписано все на "пальцах" Проще реализуется и проще работает, разные понятия... Рекурсивные обходы деревье рассказываются на младших курсах университетов, так что нового вы мало что открыли. Циклический алгоритм потребует куда меньше ресурсов (тот же стек), нежели рекурсивный. Но суть не в этом. Он не удаляет поддеревья... Хотя, как я понял, задача у него не совсем в удалении. В любом случае, алгоритм неверный, потому что он не обрабатывает поддеревья. А EgorTheBlade я бы посоветовал шевелить мозгой дальше. Это куда как приятнее, чем хватать готовые решения из гугла, а составлять алгоритм за вас вряд-ли кто-то станет...

Автор: niteo 30.7.2010, 15:06

Цитата Проще реализуется и проще работает, разные понятия... Рекурсивные обходы деревье рассказываются на младших курсах университетов, так что нового вы мало что открыли. Циклический алгоритм потребует куда меньше ресурсов (тот же стек), нежели рекурсивный. Не говорите глупостей, уважаемый.  При рекурсии передается указатель на узел дерева и адрес возврата 4 + 4 байта. Итого 8 байт в стек. Скорость выполнения RET и JMP одинаковая. При чем в вашем случае, с циклом приходится инициализировать туеву кучу переменных, не считая того что код получается вообще нечитаемым и огромным. Как я и писал, вот алгоритм из ссылки: Код Удаление узла (DEL) Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева Т узел с ключом K (если такой есть). Алгоритм:     * Если дерево T пусто, остановиться     * Иначе сравнить K со ключом X корневого узла n.           o Если K>X, рекурсивно удалить K из правого поддерева Т.           o Если K<X, рекурсивно удалить K из левого поддерева Т.           o Если K=X, то неоходимо рассмотреть два случая.                 + Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения и освобождаем память, занимаемую узлом m.                 + Если оба ребёнка присутствуют, то                       # найдём узел m, являющийся самым левым узлом правого поддерева;                       # скопируем значения полей (key, value) узла m в соответствующие поля узла n.                       # у родителя узла m заменим ссылку на узел m ссылкой на правого ребёнка узла m (который, в принципе, может быть равен nil).                       # освободим память, занимаемую узлом m (на него теперь никто не указывает, а его данные были перенесены в узел n). А вот его реализация, могут быть ошибки, но как то так, сходу написал его: Код void Del(TREE * node) {     TREE * buf_node;     if(node != NULL)     {         if(node->val > key) Del(node->R);         if(node->val < key) Del(node->L);         if(node->val == key)         if(node->R == NULL && node->L !=NULL)         {                 buf_node = node->L;             node->L = node->L->L;             node->R = node->L->R;             node->val = node->L->val;             delete buf_node;         };         if(node->L == NULL && node->R !=NULL)         {                 buf_node = node->R;             node->L = node->R->L;             node->R = node->R->R;             node->val = node->R->val;             delete buf_node;         };         if(node->L != NULL && node->R !=NULL)         {                 buf_node = node->R;             while(buf_node->L != NULL)             {                 buf_node = buf_node->L;                 }             node->val = buf_node->val;             buf_node->parent->L = buf_node->R             delete buf_node;         };     }; }

Автор: EnergoHokum 30.7.2010, 17:19

http://rain.ifmo.ru/cat/view.php/vis/trees, рекомендую. Очень полезный для понимания всяких алгоритмов ресурс.

Автор: HellStranger 30.7.2010, 17:59

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

Автор: Abyx 30.7.2010, 18:05

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

Автор: Abyx 30.7.2010, 18:25

по теме, дерево без проблем обходится парой вложенных циклов без всяких рекурсий внешний цикл перебирает все листья, внутренний - перемещается в глубину псевдокод: Код def for_each(branch, func):    i  = 0    while true:        p = branch        j = i++        while !is_leaf(p):            p = get_child(p, j % childs_count(p))            j = j / childs_count(p)        if j != 0:            return        func(p) для двусвязного дерева надо добавить откаты назад

Автор: HellStranger 30.7.2010, 21:37

Цитата(Abyx @  30.7.2010,  18:05 ) только про переходы внутри сегмента - это не применимо к x86-32 Уважаемый, вам туда же, куда и предыдущему оратору: официальный мануал Intel IA32/64 либо, на обычном русском языке Юров. Как раз в отношении других архитектур это, может быть, и не применимо, а сегментностраничную организацию памяти архитектуры Intel ещё никто не отменял. Добавлено через 1 минуту и 45 секунд Цитата(Abyx @  30.7.2010,  18:25 ) по теме, дерево без проблем обходится парой вложенных циклов без всяких рекурсий внешний цикл перебирает все листья, внутренний - перемещается в глубину А как при этом стек экономится...  Да и лишних CALL и RET нет.

Автор: Abyx 30.7.2010, 22:12

Цитата(HellStranger @  30.7.2010,  22:37 ) сегментностраничную организацию памяти архитектуры Intel ещё никто не отменял. нам читать лень, мы просто знаем  при "плоской" (flat) модели адресации основные сегменты (cs, ds, es) никакой роли не играют, их можно игнорировать. Цитата(HellStranger @  30.7.2010,  18:59 ) JMP осуществляет только ближние переходы в рамках данного семгмента, RET- любые переходы. пишите "jmp near" и "retn" Цитата(HellStranger @  30.7.2010,  22:37 ) А как при этом стек экономится... smile Да и лишних CALL и RET нет.  зато O(f(n)) сложность другая.

Автор: HellStranger 30.7.2010, 23:44

Цитата(Abyx @  30.7.2010,  22:12 ) нам читать лень, мы просто знаем smile при "плоской" (flat) модели адресации основные сегменты (cs, ds, es) никакой роли не играют, их можно игнорировать. Да уж... CS игнорируется... Откуда ж тогда код брать?..  Ну да ладно, тебе хоть сцы в глаза, скажешь божья роса, раз для тебя официальный док Intel это старый завет.  Цитата(Abyx @  30.7.2010,  22:12 ) пишите "jmp near" и "retn" Ты видел какие команды указал предыдущий оратор?.. О спецификаторе near и речи не было. Да и смысл его указывать у JMP. В соседний сегмент всё-равно не перепрыгнешь!  Цитата(Abyx @  30.7.2010,  22:12 ) зато O(f(n)) сложность другая.  Не совсем понятно за счёт чего сложность другая?.. Просматриваться будут всё-равно всё узлы последовательно, это вам не сортировка... Кстати, немного отвлечёмся от темы, результаты сравнения qsort рекурсивной и нерекурсивной пактически одинаковы, нерекурсивный вариант уступает самый мизер из-за использования стека и обращения к нему... Это отступление к тому, что при одном и том же алгоритме на его сложность совершенно не влияет наличие либо отсутствие рекурсии... Так что опять вы блеснули непонятно чем...

Автор: baldina 31.7.2010, 01:25

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

Автор: niteo 31.7.2010, 09:33

Ладно, раз уж пошел такой жесткий оффтоп, и наш "уважаемый" HellStranger все никак не успокоится... Цитата(HellStranger @  30.7.2010,  23:44 ) Да уж... CS игнорируется... Откуда ж тогда код брать?.. smile Ну да ладно, тебе хоть сцы в глаза, скажешь божья роса, раз для тебя официальный док Intel это старый завет. При flat модели памяти, код и данные используют одно и то же адресное пространство. Так что, не говори о том чего не знаешь. Цитата(HellStranger @  30.7.2010,  23:44 ) Ты видел какие команды указал предыдущий оратор?.. О спецификаторе near и речи не было. Да и смысл его указывать у JMP. В соседний сегмент всё-равно не перепрыгнешь! smile По умолчанию компилятор сделал бы в данном случае, примере что я указал, RETN. Но для вас это сложно, я понимаю. Цитата(HellStranger @  30.7.2010,  21:37 ) А как при этом стек экономится... smile Да и лишних CALL и RET нет.  Про развертку стека почитайте. Стек в процессорах семейства Intel поддерживается на аппаратном уровне. Уже говорилось, что QuickSort реализована "разверткой" рекурсии. И делается это для того, чтобы скомпилированный код был компактен, так как со стеком проще работать, и не плодить немыслимое количество условных переходов. А по поводу ваших речей на форуме, у вас человек попросил помощи, а вы вместо того чтобы дать конкретный кусок кода, или же сослаться на статью, которая помогла бы, а вы начинаете изливать неудержимым фонтаном ваши мысли по поводу форумчан...  Предлагаю вам реализовать вышеописанный алгоритм на циклах, вот и сравним, у кого код меньше и быстрее...

Автор: HellStranger 31.7.2010, 21:16

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

Автор: HellStranger 31.7.2010, 21:36

Цитата(niteo @  31.7.2010,  09:33 ) По умолчанию компилятор сделал бы в данном случае, примере что я указал, RETN. Но для вас это сложно, я понимаю. Доказательство полной некомпетентности- утверждение "По умолчанию компилятор сделал бы в данном случае". Каждый производитель компиляторов возврат из функий оптимизирует по своему! Вы много дизасэмблированного различными компиляторами кода видели?.. Про модель памяти flat мне тоже заливать не надо, далеко не везде используется эта модель памяти. Цитата(niteo @  31.7.2010,  09:33 ) Про развертку стека почитайте. Стек в процессорах семейства Intel поддерживается на аппаратном уровне. Уже говорилось, что QuickSort реализована "разверткой" рекурсии. И делается это для того, чтобы скомпилированный код был компактен, так как со стеком проще работать, и не плодить немыслимое количество условных переходов. Стек для процессора- эта такая же область памяти, как и все остальные! Это не какой-то отдельный жёстко зашитый адресный диапазон, работа с которым как-то жутко ускорена! То, что вы в архитектуре абсолютно ни черта не понимаете, это сразу бросается в глаза. Так что не умничайте впредь! Если говорите что-то почитать, то давайте хотя-бы автора, названия книги от вас не дождёшься, это ясно... Цитата(niteo @  31.7.2010,  09:33 ) А по поводу ваших речей на форуме, у вас человек попросил помощи, а вы вместо того чтобы дать конкретный кусок кода, или же сослаться на статью, которая помогла бы, а вы начинаете изливать неудержимым фонтаном ваши мысли по поводу форумчан...  По поводу реализации я уже объяснил, что вряд-ли кто-то будет тратить своё время не реализацию алгоритма. Меряться письками на интерес, мне за это не платят на работе! А будет проект по данной тематике- специально выложу код! Я здесь много раз помощи просил чисто даже в плане документации или разъяснения (код не просил никогда!), и на мои вопросы ДО СИХ ПОР НЕ БЫЛО НИ ОДНОГО ОТВЕТА! Так что заглохни со своей критикой, а читай книжки!

Автор: niteo 31.7.2010, 22:40

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

Автор: HellStranger 31.7.2010, 22:54

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

Автор: baldina 3.8.2010, 17:49

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

Автор: HellStranger 4.8.2010, 12:02

Цитата(baldina @  3.8.2010,  17:49 ) ты меня к Вирту отправил?  Да. Алгоритны и структуры данных. Второе издание. Тебе ещё страницу сказать, где результаты сравнения указаны?..

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)