6 / 6 / 3
Регистрация: 22.09.2013
Сообщений: 166
|
|
|
1
|
Красно черное дерево(Вставка)
18.01.2015, 13:55. Показов 1879. Ответов 0
Требуется написать для красно черного дерева функцию вставки. При написании возникли проблемы. Помогите исправить.
В 66 строке необработанное исключение
//Tree.h
| 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
| #include <iostream>
#include <conio.h>
#include <windows.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
/* структура, описывающая узел красно-черного дерева */
struct rb_node
{
int red;
int data;
struct rb_node *link[2];
};
//Структура описывающая красно черное дерево
struct rb_tree
{
struct rb_node *root; // указатель на корневой узел
int count; // количество узлов в дереве
};
//Определение цвета узла
int is_red(struct rb_node *node)
{
return node != NULL && node->red == 1;
}
/* функция для однократного поворота узла */
struct rb_node *rb_single(struct rb_node *root, int dir)
{
struct rb_node *save = root->link[!dir];
root->link[!dir] = save->link[dir];
save->link[dir] = root;
root->red = 1;
save->red = 0;
return save;
}
/* функция для двукратного поворота узла */
struct rb_node *rb_double(struct rb_node *root, int dir)
{
root->link[!dir] = rb_single(root->link[!dir], !dir);
return rb_single(root, dir);
}
struct rb_node *make_node(int data)
{
struct rb_node *rn = new rb_node;
if (rn != NULL) {
rn->data = data;
rn->red = 1; /* –инициализация красным цветом */
rn->link[0] = NULL;
rn->link[1] = NULL;
}
return rn;
}
int rb_insert(struct rb_tree *tree, int data)
{
/* если добавляемый элемент оказывается первым – то ничего делать не нужно*/
if (tree->root == NULL) {
tree->root = make_node(data);
if (tree->root == NULL)
return 0;
}
else {
struct rb_node head = { 0 }; /* временный корень дерева*/
struct rb_node *g, *t; /* дедушка и родитель */
struct rb_node *p, *q; /* родитель и итератор */
int dir = 0, last;
/* вспомогательные переменные */
t = &head;
g = p = NULL;
q = t->link[1] = tree->root;
/* основной цикл прохода по дереву */
for (;;)
{
if (q == NULL) {
/* вставка ноды */
p->link[dir] = q = make_node(data);
tree->count++;
if (q == NULL)
return 0;
}
else if (is_red(q->link[0]) && is_red(q->link[1]))
{
/* смена цвета */
q->red = 1;
q->link[0]->red = 0;
q->link[1]->red = 0;
}
/* совпадение 2-х красных цветов */
if (is_red(q) && is_red(p))
{
int dir2 = t->link[1] == g;
if (q == p->link[last])
t->link[dir2] = rb_single(g, !last);
else
t->link[dir2] = rb_double(g, !last);
}
/* такой узел в дереве уже есть - выход из функции*/
if (q->data == data)
{
break;
}
last = dir;
dir = q->data < data;
if (g != NULL)
t = g;
g = p, p = q;
q = q->link[dir];
}
/* обновить указатель на корень дерева*/
tree->root = head.link[1];
}
/* сделать корень дерева черным */
tree->root->red = 0;
return 1;
} |
|
//Main.cpp
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
| #include "Tree.h"
int main()
{
struct rb_tree * my_tree = new rb_tree;
my_tree = NULL;
rb_insert(my_tree, 10);
_getch();
return 0;
} |
|
0
|
(
