Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.78/18: Рейтинг темы: голосов - 18, средняя оценка - 4.78
11 / 12 / 8
Регистрация: 16.11.2016
Сообщений: 892
1

Поиск в двоичном дереве: Красно-чёрное дерево.

12.02.2018, 11:55. Показов 3366. Ответов 7
Метки нет (Все метки)

Искал в интернете, либо сложные коды в тысячу строк, либо непонятные термины (в теории о красно-чёрных деревьях не встречались). Читал что достаточно популярно, не могли бы Вы скинуть свою реализацию Красно-чёрного дерева на С++ (желательно не сложную). Спасибо.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.02.2018, 11:55
Ответы с готовыми решениями:

Красно-чёрное дерево
Здравствуйте! мне нужно создать красное-чёрное дерево...посоветуйте простой понятный учебник или...

Поиск в красно-черном дереве
Доброе утро! Изучая, Стандарт выполняю задание - создайте шаблон ассоциативного контейнера. В...

Поиск в двоичном дереве
Добрый день. Нужно построить англо-русский словарь как двоичное дерево. Каждая компонента содержит...

NIL в красно-черном дереве
В Кормене, алгоритм добавления содержит значение NIL, а в алгоритме удаление говорится о...

7
184 / 192 / 48
Регистрация: 25.08.2011
Сообщений: 793
12.02.2018, 12:06 2
Ищем по форуму думаю уже что то такое есть
0
11 / 12 / 8
Регистрация: 16.11.2016
Сообщений: 892
12.02.2018, 12:47  [ТС] 3
Поискал по форуму, нашёл вот это Красно-черное дерево. Обход дерева в глубину . Подскажите пожалуйста, это Красно-чёрное дерево? По-моему нет.
0
2723 / 1887 / 559
Регистрация: 05.06.2014
Сообщений: 5,499
12.02.2018, 13:01 4
Цитата Сообщение от triatri3 Посмотреть сообщение
Искал в интернете, либо сложные коды в тысячу строк, либо непонятные термины (в теории о красно-чёрных деревьях не встречались).
В Википедию и читать вдумчиво, глядя на иллюстрации. И нет, кратенько не получится. Ибо алгоритм представляет собой длинный список "ежели дерево такой формы - поверни его так, а ежели сякой, то поверни сяк".

Добавлено через 1 минуту
И вообще, берите АВЛ-дерево. Алгоритм там куда попроще, а ТТХ примерно те же самые (что круче - тема холиварная).
0
11 / 12 / 8
Регистрация: 16.11.2016
Сообщений: 892
13.02.2018, 08:15  [ТС] 5
Я читал, в том числе и Википедию. Я про то, что в структуре дерева нет цвета, так ведь? Поэтому это не КЧД.
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
#include "stdafx.h"
#include <deque> 
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t) 
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
   
    std::cout<<t->info<<std::endl; //И показываем элемент
    print(t->l);
    print(t->r);
    }
        
}
 
void main ()
{   
    int n; //Количество элементов
    int s;//Число, передаваемое в дерево
    int v;// Высота
    int degree; // степень графа 
    cout<<"Type number of elements  ";
    cin>>n; //Вводим количество элементов
    if (n%2!=1) {
        v = n/2;
    }
    else { 
        v = n/2 -0,5;};
        cout<<"Height of the tree = ";
        cout<<v;
        cout<<"\n";
        degree = n-1;
        cout<<"Degree of the tree =  ";
        cout<<degree;
        cout<<"\n";
 
 
    for (int i=0;i<n;++i)
    {  
    cout<<"\nType number ";
    cin>>s; //Считываем элемент за элементом
   
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"Your tree is:\n";
    print(tree);
   system("pause");      
}
0
2723 / 1887 / 559
Регистрация: 05.06.2014
Сообщений: 5,499
13.02.2018, 13:59 6
Цитата Сообщение от triatri3 Посмотреть сообщение
Я читал, в том числе и Википедию. Я про то, что в структуре дерева нет цвета, так ведь?
В примерах из Википедии поле color таки есть. Я же сказал, читать вдумчиво.
0
2228 / 1731 / 865
Регистрация: 21.12.2010
Сообщений: 3,074
Записей в блоге: 11
13.02.2018, 16:08 7
Лучший ответ Сообщение было отмечено triatri3 как решение

Решение

вот, сделаны вставка и поиск узлов (без удаления), сделано по статье в википедии
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include <iostream>
 
enum COLOR {RED, BLACK};
 
struct node
{
    node(int const rhs) : data(rhs){}
    COLOR color = RED;
    int data;
    node* left = nullptr, *right = nullptr, *parent = nullptr;
};
 
// дерево
node* root = nullptr;
 
// поиск деда
node* grandparent(node* rhs)
{
    node* ret = nullptr;
    if (rhs && rhs->parent)
    {
        ret = rhs->parent->parent;
    }
    
    return ret;
}
 
// поиск дяди
node* uncle(node* rhs)
{
    node* ret = nullptr;
    if (node const* gp = grandparent(rhs))
    {
        ret = (gp->left == rhs->parent ? gp->right : gp->left);
    }
 
    return ret;
}
 
// левый поворот
void rotate_left(node* rhs)
{
    node* pivot = rhs->right;
 
    pivot->parent = rhs->parent; 
    if (rhs->parent != nullptr) 
    {
        if (rhs->parent->left == rhs)
        {
            rhs->parent->left = pivot;
        }
        else
        {
            rhs->parent->right = pivot;
        }   
    }
    else
    {
        root = pivot;
    }
 
    rhs->right = pivot->left;
    if (pivot->left != nullptr)
    {
        pivot->left->parent = rhs;
    }
    
    rhs->parent = pivot;
    pivot->left = rhs;
}
 
// правый поворот
void rotate_right(node* rhs)
{
    node* pivot = rhs->left;
 
    pivot->parent = rhs->parent; 
    if (rhs->parent != nullptr) 
    {
        if (rhs->parent->left == rhs)
        {
            rhs->parent->left = pivot;
        }
        else
        {
            rhs->parent->right = pivot;
        }
    }
    else
    {
        root = pivot;
    }
 
    rhs->left = pivot->right;
    if (pivot->right != nullptr)
    {
        pivot->right->parent = rhs;
    }
 
    rhs->parent = pivot;
    pivot->right = rhs;
}
 
 
void push_case1(node*);
void push_case2(node*);
void push_case3(node*);
void push_case4(node*);
void push_case5(node*);
 
// вставка
void push(node*& root, int const data)
{
    node** pcur = &root;
    node* parent = nullptr;
    while(*pcur)
    {
        parent = *pcur;
        if (data < (*pcur)->data)
        {
            pcur = &(*pcur)->left;
        }
        else if (data > (*pcur)->data)
        {
            pcur = &(*pcur)->right;
        }
        else
        {
            break;
        }
    }
    if (nullptr == *pcur)
    {
        *pcur = new node(data);
        (*pcur)->parent = parent;
 
        push_case1(*pcur);
    }
}
 
void push_case1(node* rhs)
{
    if (rhs->parent == nullptr)
    {
        rhs->color = BLACK;
    }
    else
    {
        push_case2(rhs);
    }
}
 
void push_case2(node *n)
{
    if (n->parent->color == BLACK)
    {
        return; /* Tree is still valid */
    }
    else
    {
        push_case3(n);
    }
}
 
void push_case3(node *n)
{
    node *u = uncle(n), *g = nullptr;
 
    if ((u != nullptr) && (u->color == RED))
    {
        // && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным.
        n->parent->color = BLACK;
        u->color = BLACK;
        g = grandparent(n);
        g->color = RED;
        push_case1(g);
    }
    else 
    {
        push_case4(n);
    }
}
 
void push_case4(node *n)
{
    node *g = grandparent(n);
 
    if ((n == n->parent->right) && (n->parent == g->left)) 
    {
        rotate_left(n->parent);
        n = n->left;
    }
    else if ((n == n->parent->left) && (n->parent == g->right)) 
    {
        rotate_right(n->parent);
        n = n->right;
    }
    push_case5(n);
}
 
void push_case5(node *n)
{
    node *g = grandparent(n);
 
    n->parent->color = BLACK;
    g->color = RED;
    if ((n == n->parent->left) && (n->parent == g->left)) 
    {
        rotate_right(g);
    }
    else 
    { /* (n == n->parent->right) && (n->parent == g->right) */
        rotate_left(g);
    }
}
 
// поиск
node* find(int const data)
{
    node* ret = root;
    while (ret)
    {
        if (data < ret->data)
        {
            ret = ret->left;
        }
        else if (data > ret->data)
        {
            ret = ret->right;
        }
        else
        {
            break;
        }
    }
 
    return ret;
}
 
 
 
// печать дерева
void print(node* root, int indent = 0)
{
    if (root)
    {
        print(root->right, indent + 1);
        for (int i = 0; i < indent; ++i)
        {
            std::cout << ".";
        }
        std::cout << root->data << std::endl; 
        print(root->left, indent + 1);
    }
}
 
 
int main()
{
    push(root, 5);
    push(root, 6);
    push(root, 7);
    push(root, 5);
 
    print(root);
 
    if (node* found = find(5))
    {
        std::cout << "\nfound: " << found->data << std::endl;
    }
    
}
1
11 / 12 / 8
Регистрация: 16.11.2016
Сообщений: 892
20.02.2018, 09:34  [ТС] 8
Спасибо, не могли бы Вы (кто-нибудь) добавить к коду выше (от igorrr37) операцию удаления элемента?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.02.2018, 09:34

Красно-черное дерево
Добрый вечер. Понимаю что вопрос уже много раз поднимался, но я запутываюсь в выложенных решениях....

Красно-черное дерево
Здраствуйте. Есть такое задание, вывести на экран все черные вершины красно-черного дерева. С...

Представление выражения в двоичном дереве
есть выражение 4*a/2 мне надо его упростить и получить 2*a т.е. я ввожу в программу 4*a/2,...

Реализация словаря в двоичном дереве поиска
Помогите,пожалуйста, создать программу на С++! Тема: Релизация словаря в двоичном дереве...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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