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

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

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

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

04.04.2013, 15:01. Просмотров 621. Ответов 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++
Помогите пожалуйста! Необходимо написать программу, которая для двух вершин дерева определяет, является ли одна из них предком другой. ...

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

Разобраться в бинарном дереве - C++
Нашел вот такой вариант построения бинарного дерева. Просьба прокомментировать строки кода которые выделил ниже: #include...

Строки в бинарном дереве - C++
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в соответствующий объект этого класса на...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 15:17 #2
Нет кодом я не подскажу просто в теории у тебя есть адрес узла который ты хочешь удалить. Ну ты допустим стоишь в предыдущем узле и через указатель на перед делаешь проверку ага этот узел имеет искомое значение значит мы его будем удалять. Вот у тебя есть указатель на этот узел который нужно удалить ты его делаешь равным нулю. Перед этим адрес узла который ты хотел удалить присваиваешь промежуточному указателю, он тебе пригодится для освобождения памяти. Тебе просто нужно память высвободить, потому что за время работы программы может закончится память, система будет ее считать занятой, хотя на самом деле она свободна для программы просто не освободившаяся для системы.
Дальш ты берешь это промежуточный указатель и рекурсивно обходишь каждый узел начиная с низов я непомню как этот обход называется и затем delete адрес самого нижнего делаешь, Ну как это можно представить от допустим у тебя есть придпоследний узел ты сейчас стоишь в нем делаешь через указатель на последний узел то есть проверку указателя последнего узла если он равен нулю, то это последний и можно delete использовать делаешь delete и адресс этого узла. Токо обход нужно делать правильный.

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

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

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

Добавлено через 53 секунды
Не помню как я это делал но помню мучился несколько часов. Это точно.
xtorne21st
интересующийся
304 / 275 / 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
интересующийся
304 / 275 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 19:52  [ТС] #7
ya_noob, Я тут еле-еле нагуглил алгоритм удаление звена (сам как-то не допёр). А вы говорите об оптимизации...

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

Ваша задача заключается в том, чтобы найти оптимальный способ поднять тот узел в корень поддерева В. (подсказка: ищите инфу про повороты в бинарном дереве)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 20:28
Привет! Вот еще темы с ответами:

Подсчет вершин в бинарном дереве - C++
Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного дерева T(корень считать вершиной 0-го...

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
04.04.2013, 20:28
Ответ Создать тему
Опции темы

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