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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
#1

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

04.04.2013, 15:01. Просмотров 587. Ответов 7
Метки нет (Все метки)

Добрый день. У меня получился сильно громоздкий код для удаление узла дерева (не корня).
Нет никаких идей по поводу упрощения. Может кто-то подскажет, как сделать всё более компактно?
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++
Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного дерева T(корень считать вершиной 0-го...

Оператор присвоения в бинарном дереве - C++
Не смог разобраться. Прокомментируйте, будьте добры. Задание такое, определите стандартный конструктор и функции управления...

Сумма чисел в бинарном дереве - C++
Выбрать уровень(глубину, высоту) бинарного дерева и посчитать сумму чисел(в вершинах), находящихся на этом уровне. P.S. Дерево построено,...

Количество листьев в бинарном дереве - C++
Задача: Найти количество листьев в дереве. Собственно ввод и вывод дерева есть: #include &lt;iostream.h&gt; #include &lt;iomanip.h&gt; ...

Удалить узел в бинарном дереве - C++
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего удалить найденный узел из дерева. В структуре...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 15:18  [ТС]     Простая организация удаление узла в бинарном дереве #3
Цитата Сообщение от ninja2 Посмотреть сообщение
Дальш ты берешь это промежуточный указатель и рекурсивно обходишь каждый узел начиная с низов я непомню как этот обход называется и затем delete адрес самого нижнего делаешь, Ну как это можно представить от допустим у тебя есть придпоследний узел ты сейчас стоишь в нем делаешь через указатель на последний узел есть проверку указателя последнего узла если он равен нулю, то это последний и можно delete использовать делаешь delete и адресс этого узла. Токо обход нужно делать правильный.
У меня код работает правильно. Беда в том что он занимает по размеру больше чем все остальные функции вместе взятые.

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

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

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

Добавлено через 1 минуту
Имхо, удаление узла самая сложная часть в "дереве".
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.04.2013, 16:58     Простая организация удаление узла в бинарном дереве #6
крайне неудачная реализация удаления узла. я верю, что удаление работает правильно, но такое удаление сильно разбалансирует дерево, точнее "вытягивает" его влево или вправо (т.е. в худшем случае узлы в дереве будут иметь только либо левых потомков либо правых) и всё преимущество при поиске по сравнению с последовательным поиском исчезнет.
Ищите другой подход к удалению узла, точнее другой подход к слиянию поддеревьев удаляемого узла (это была подсказка если что )
xtorne21st
интересующийся
303 / 274 / 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++
Вот функция поиска предка в бинарном дереве поиска: tree* predok(tree* root, tree* potomok, int n = -1){ n++; printf(&quot;%d...

Поиск ключа в бинарном дереве поиска - C++
Здравствуйте! Помогите ещё с задачками) 1.Поиск ключа в бинарном дереве поиска (точное соответствие). 2. Поиск ключа в бинарном...

Необычная функция в бинарном дереве поиска - C++
Здравствуйте, уважаемые форумчане. Очень прошу Вашей помощи. Задание: Реализовать структуру данных двоичное дерево поиска,...

Поиск одинаковых элементов в бинарном дереве - C++
Нужно вывести на экран все повторяющиеся элементы в бинарном дереве. # include &lt;iostream&gt; # include &lt;conio.h&gt; using namespace...

Поиск одинаковых элементов в бинарном дереве. - C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести на экран все одинаковые элементы в...


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

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru