Форум программистов, компьютерный форум CyberForum.ru

Простая организация удаление узла в бинарном дереве - C++

Восстановить пароль Регистрация
 
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 15:01     Простая организация удаление узла в бинарном дереве #1
Добрый день. У меня получился сильно громоздкий код для удаление узла дерева (не корня).
Нет никаких идей по поводу упрощения. Может кто-то подскажет, как сделать всё более компактно?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
struct BinTree
{
    int key;
    BinTree* left_node;
    BinTree* right_node;
};
 
// Удалиние узла (не корня). Возращает истину при удачном удалении узла.
bool free_node(BinTree* root, int key)
{
    if (!root)
    {
        return false;
    }
 
    // Если левый узел соответствует искомому ключу.
    if (root->left_node && root->left_node->key == key)
    {
        // Если обе ветки пустые.
        if (!root->left_node->left_node && !root->left_node->right_node)
        {
            delete root->left_node;
            root->left_node = NULL;
            return true;
        }
        // Если правая ветка пустая.
        if (root->left_node->left_node && !root->left_node->right_node)
        {
            BinTree* tmp = root->left_node;
            root->left_node = root->left_node->left_node;
            delete tmp;
            return true;
        }
        // Если левая ветка пустая.
        if (root->left_node->right_node && !root->left_node->left_node)
        {
            BinTree* tmp = root->left_node;
            root->left_node = root->left_node->right_node;
            delete tmp;
            return true;
        }
        // Если обе ветки имеют узлы.
        if (root->left_node->left_node && root->left_node->right_node)
        {
            BinTree* tmp_need = root->left_node; // запомним удаляемый узел.
            BinTree* tmp_node = root->left_node->left_node; // запомним левый узел.
            root->left_node = root->left_node->right_node; // присоединим правый узел.
            BinTree* tmp_left = root->left_node; // запомним, для поиска "дна".
 
            while (tmp_left->left_node)
            {
                tmp_left = tmp_left->left_node;
            }
 
            tmp_left->left_node = tmp_node;
            delete tmp_need;
            return true;
        }
    }
 
    // Аналогично и для правой части.
    if (root->right_node && root->right_node->key == key)
    {
        if (!root->right_node->left_node && !root->right_node->right_node)
        {
            delete root->right_node;
            root->right_node = NULL;
            return true;
        }
        if (root->right_node->left_node && !root->right_node->right_node)
        {
            BinTree* tmp = root->right_node;
            root->right_node = root->right_node->left_node;
            delete tmp;
            return true;
        }
        if (root->right_node->right_node && !root->right_node->left_node)
        {
            BinTree* tmp = root->right_node;
            root->right_node = root->right_node->right_node;
            delete tmp;
            return true;
        }
        if (root->right_node->left_node && root->right_node->right_node)
        {
            BinTree* tmp_need = root->right_node;
            BinTree* tmp_node = root->right_node->left_node;
            root->right_node = root->right_node->right_node;
            BinTree* tmp_right = root->right_node;
 
            while (tmp_right->left_node)
            {
                tmp_right = tmp_right->left_node;
            }
 
            tmp_right->left_node = tmp_node;
            delete tmp_need;
            return true;
        }
    }
 
    if (key < root->key)
    {
        free_node(root->left_node, key); // Если ключ меньше - пойдём налево.
    }
 
    if (key > root->key)
    {
        free_node(root->right_node, key); // Если ключ больше - направо.
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2013, 15:01     Простая организация удаление узла в бинарном дереве
Посмотрите здесь:

C++ Удаление элемента(узла) в бинарном дереве
C++ Количество листьев в бинарном дереве
Поиск в Бинарном Дереве! C++
Сумма чисел в бинарном дереве C++
Строки в бинарном дереве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 15:17     Простая организация удаление узла в бинарном дереве #2
Нет кодом я не подскажу просто в теории у тебя есть адрес узла который ты хочешь удалить. Ну ты допустим стоишь в предыдущем узле и через указатель на перед делаешь проверку ага этот узел имеет искомое значение значит мы его будем удалять. Вот у тебя есть указатель на этот узел который нужно удалить ты его делаешь равным нулю. Перед этим адрес узла который ты хотел удалить присваиваешь промежуточному указателю, он тебе пригодится для освобождения памяти. Тебе просто нужно память высвободить, потому что за время работы программы может закончится память, система будет ее считать занятой, хотя на самом деле она свободна для программы просто не освободившаяся для системы.
Дальш ты берешь это промежуточный указатель и рекурсивно обходишь каждый узел начиная с низов я непомню как этот обход называется и затем delete адрес самого нижнего делаешь, Ну как это можно представить от допустим у тебя есть придпоследний узел ты сейчас стоишь в нем делаешь через указатель на последний узел то есть проверку указателя последнего узла если он равен нулю, то это последний и можно delete использовать делаешь delete и адресс этого узла. Токо обход нужно делать правильный.

Добавлено через 5 минут
там все это удаление делается в две функции мб можно делать в одну но вде del(указатель на узел)- это функция которая вызывается при удалении. и delHelper(указатель на узел) - эта рекурсивная которая вызывается если узел не последний, а имеет еще под собой узлы.
в del делается проверка если узел один то он просто удаляется, а если не один то просто вызов delHelper()
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 15:18  [ТС]     Простая организация удаление узла в бинарном дереве #3
Цитата Сообщение от ninja2 Посмотреть сообщение
Дальш ты берешь это промежуточный указатель и рекурсивно обходишь каждый узел начиная с низов я непомню как этот обход называется и затем delete адрес самого нижнего делаешь, Ну как это можно представить от допустим у тебя есть придпоследний узел ты сейчас стоишь в нем делаешь через указатель на последний узел есть проверку указателя последнего узла если он равен нулю, то это последний и можно delete использовать делаешь delete и адресс этого узла. Токо обход нужно делать правильный.
У меня код работает правильно. Беда в том что он занимает по размеру больше чем все остальные функции вместе взятые.

Цитата Сообщение от ninja2 Посмотреть сообщение
Дальш ты берешь это промежуточный указатель и рекурсивно обходишь каждый узел начиная с низов я непомню как этот обход называется и затем delete адрес самого нижнего делаешь,
И не ясно зачем мне удалять самый нижний, может быть он мне ещё пригодится?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 15:25     Простая организация удаление узла в бинарном дереве #4
А да я вспомнил то чуток перепутал, то просто удаление всего узла.

Добавлено через 55 секунд
Вспомнил там свой алгоритм. Короче запутаная фигня. Ну раз работает правильно, то и не парся фиг сним что большой.

Добавлено через 53 секунды
Не помню как я это делал но помню мучился несколько часов. Это точно.
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 15:27  [ТС]     Простая организация удаление узла в бинарном дереве #5
Цитата Сообщение от ninja2 Посмотреть сообщение
там все это удаление делается в две функции
Вторая функция необходима для удаление корня. Если искомый ключ как раз таки является корнем, то функция после удаления завершится (возвратит значение), иначе она вызовет функция для удаления других узлов. Как то так, но речь сейчас не об этом.
Если вы имеете ввиду дополнительную функцию для упращения, то я не представляю как её можно организовать и "запихнуть" в мой код.

Добавлено через 1 минуту
Имхо, удаление узла самая сложная часть в "дереве".
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.04.2013, 16:58     Простая организация удаление узла в бинарном дереве #6
крайне неудачная реализация удаления узла. я верю, что удаление работает правильно, но такое удаление сильно разбалансирует дерево, точнее "вытягивает" его влево или вправо (т.е. в худшем случае узлы в дереве будут иметь только либо левых потомков либо правых) и всё преимущество при поиске по сравнению с последовательным поиском исчезнет.
Ищите другой подход к удалению узла, точнее другой подход к слиянию поддеревьев удаляемого узла (это была подсказка если что )
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 19:52  [ТС]     Простая организация удаление узла в бинарном дереве #7
ya_noob, Я тут еле-еле нагуглил алгоритм удаление звена (сам как-то не допёр). А вы говорите об оптимизации...

Добавлено через 4 минуты
Цитата Сообщение от ya_noob Посмотреть сообщение
Ищите другой подход к удалению узла, точнее другой подход к слиянию поддеревьев удаляемого узла
Есть пару идей, но при удалении звена придётся перестраивать пол дерева, что тоже не совсем хорошо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 20:28     Простая организация удаление узла в бинарном дереве
Еще ссылки по теме:

Поиск предка элемента в бинарном дереве C++
Поиск дубликатов в бинарном дереве C++
C++ Разобраться в бинарном дереве

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.04.2013, 20:28     Простая организация удаление узла в бинарном дереве #8
Цитата Сообщение от xtorne21st Посмотреть сообщение
А вы говорите об оптимизации...
нет, я говорю о том, что ваш алгоритм ухудшает структуру дерева. нужен другой подход.
Цитата Сообщение от xtorne21st Посмотреть сообщение
Есть пару идей, но при удалении звена придётся перестраивать пол дерева, что тоже не совсем хорошо.
Идея такая: удаляемый узел в общем случае имеет 2 поддерева A и B. Все узлы в поддереве В больше чем в поддереве А. Если получится поднять самый младший узел в поддереве В в корень, то у него не будет левого потомка. Вот сюда то и нужно будет вставить поддерево А, т.к. все узлы А меньше чем новый корень поддерева В.

Ваша задача заключается в том, чтобы найти оптимальный способ поднять тот узел в корень поддерева В. (подсказка: ищите инфу про повороты в бинарном дереве)
Yandex
Объявления
04.04.2013, 20:28     Простая организация удаление узла в бинарном дереве
Ответ Создать тему
Опции темы

Текущее время: 15:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru