0 / 0 / 0
Регистрация: 13.09.2020
Сообщений: 89
1

Алгоритм АВЛ-Деревьев

12.05.2021, 11:58. Показов 211. Ответов 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
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
#include <iostream>
#include<iomanip>
#include <time.h>
#include <vector>
#include <fstream>
using namespace std;
 
vector<int> numbers;
 
struct node
{
public:
    int data, height;
    node* leftChild, * rightChild;
};
 
node* root = NULL;
 
int findMin(node* p) // finds the smallest node in the tree
{
    while (p->leftChild != NULL)
        p = p->leftChild;
    return p->data;
}
int findMax(node* p) // finds the largest node in the tree
{
    while (p->rightChild != NULL)
        p = p->rightChild;
    return p->data;
}
int max(int a, int b) // gets the max of two integers
{
    if (a > b)
        return a;
    else
        return b;
}
int height(node* p) // gets the height of the tree
{
    if (p == NULL)
        return -1;
    else
    {
        p->height = max(height(p->leftChild), height(p->rightChild)) + 1;
    }
    return p->height;
}
node* newNode(int element) // helper function to return a new node with empty subtrees
{
    node* newPtr = new node;
    newPtr->data = element;
    newPtr->leftChild = NULL;
    newPtr->rightChild = NULL;
    newPtr->height = 1;
    return newPtr;
}
void newHeight(node* p)
{
    double leftHeight = height(p->leftChild);
    double rightHeight = height(p->rightChild);
    if (leftHeight > rightHeight)
        p->height = leftHeight;
    else
        p->height = rightHeight;
}
 
node* rightRotate(node* p) // the right rotation round p
{
    node* q = p->leftChild;
    p->leftChild = q->rightChild;
    q->rightChild = p;
    newHeight(p);
    newHeight(q);
    return q;
}
 
node* leftRotate(node* q) // the left rotation round q
{
    node* p = q->rightChild;
    q->rightChild = p->leftChild;
    p->leftChild = q;
    newHeight(q);
    newHeight(p);
    return p;
}
 
node* getBalance(node* p) // p node balance
{
    newHeight(p);
    if (getBalance(p)==(node*)2)
    {
        if (getBalance(p->rightChild) < 0)
            p->rightChild = rightRotate(p->rightChild);
        return leftRotate(p);
    }
    if (getBalance(p)==(node*)-2)
    {
        if (getBalance(p->leftChild) > 0)
            p->leftChild = leftRotate(p->leftChild);
        return rightRotate(p);
    }
    return p; // no balance needed
}
 
node* insert(node* p, int element) // k key insertion in the tree with p root
{
    if (!p) return newNode(element);
    if (element < p->data)
        p->leftChild = insert(p->leftChild, element);
    else
        p->rightChild = insert(p->rightChild, element);
    return getBalance(p);
}
void inorder(node* p)
{
    if (p != NULL)
    {
        inorder(p->leftChild);
        cout << p->data << ", ";
        inorder(p->rightChild);
    }
}
void preorder(node* p)
{
    if (p != NULL)
    {
        cout << p->data << ", ";
        preorder(p->leftChild);
        preorder(p->rightChild);
    }
}
 
void print(node* root)
{
    /*cout << "Min Value: " << findMin(root) << endl;
    cout << "Max Value: " << findMax(root) << endl;
    cout << "Pre Order: ";
    preorder(root); */
    cout << endl << "Inorder: ";
    inorder(root);
    cout << endl << endl << endl << endl;
 
}
 
void read()
{
    int num;
    ifstream file_save("D://hello.txt");
    if (file_save.is_open())
    {
        while (!file_save.eof())
        {
            file_save >> num;
            numbers.push_back(num);
        }
        file_save.close();
    }
    else
    {
        cout << "Error in opening file!!" << endl;
    }
}
 
int main()
{
    double duration;
    clock_t begin = clock();
 
    read();
    int x = 0;
    int track = 0;
    for (std::vector<int>::const_iterator i = numbers.begin(); i != numbers.begin() + 100000; i++)
    {
        root = insert(root, numbers[x]);
        x++;
        track++;
        if ((track % 10000) == 0)
        {
            cout << track << " iterations" << endl;
            clock_t now = clock();
            cout << now - begin << " seconds" << endl;
        }
 
    }
    clock_t end = clock();
    duration = end - begin;
    
    cout << "The algorithm took " << duration << " seconds to complete." << endl;
    return 0;
}
Пишет, переполнение, но не понимаю, почему
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.05.2021, 11:58
Ответы с готовыми решениями:

Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено
1)Учащиеся 8-х классов участвовали в посадке деревьев. 8-а посадил 100 деревьев, 8-б —122 дерева,...

Алгоритм добавления в АВЛ-дерево
using System; using System.Collections.Generic; namespace AVL_Tree___Task_3 { ///...

Алгоритм для деревьев
Всем привет! Препод дал задание написать программу, которая бы находила максимальное независимое...

алгоритм балансировки деревьев по высоте
Всем приятного времени суток. Хотелось бы очень узнать и почитать о данном алгоритме. Подскажите с...

1
129 / 81 / 49
Регистрация: 10.01.2020
Сообщений: 293
12.05.2021, 12:07 2
Morody, в маин так попробуйте:
C++
1
2
3
4
for (auto i = numbers.begin(); i != numbers.end(); i++)
{
//  .  .  .  //
}
И в чем смысл в цикле const_iterator делать?

Добавлено через 1 минуту
либо так:
C++
1
2
3
4
for (auto &i : numbers)
{
//  .  .  .  //
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.05.2021, 12:07
Помогаю со студенческими работами здесь

Алгоритм генерации графов и деревьев
Добрый день. Подскажите пожалуйста алгоритм генерирования графов и деревьев и как это реализовать в...

Алгоритм поиска всех деревьев в графе
Имеется граф. Необходимо найти множество всех деревьев. Где дерево это минимальная неизбыточная...

Реализовать алгоритм организации и обработки информации с помощью В-деревьев
Добрый день форумчане. Появилась необходимость реализовать алгоритм организации и обработки...

Методы обхода деревьев. Особенности и применение. Прошивка деревьев
Необходимо как можно больше информации по данной теме. Причем именно чистая дискретная математика,...

АВЛ-деревья
Скинте код на Си (++) по АВЛ. как можно проще, чтоб код легче разобрать. Не могу врубиться как...

Авл Деревья
Здраствуйте прошу помощи в решении задачи. Зарание спасибо! Узел дерева содержит информацию о...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru