Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Проект "Книжная библиотека" Добрые люди, помогите пожалуйста, оформить проект "книжная библиотека". Исходный код имеется в содержащем файле project library, подскажите пожалуйста что нужно убрать, подправить, изменить.... https://www.cyberforum.ru/ cpp-beginners/ thread2828512.html Способы задания графов C++
1. Создать программу, которая будет хранить в компьютере заданный граф следующими способами: а) матрицей смежности б) матрицей инцидентности в) списком ребер г) списком смежности. Предусмотреть...
C++ бинарные деревья 1. Написать программу, в которой данные вашего варианта структуры записываются в деревья (использовать три поля для узла - текстовое данное и два числовые. Например, узел дерева содержит такую... https://www.cyberforum.ru/ cpp-beginners/ thread2828508.html C++ Особые виды очередей 1. Реализовать основные функции по работе с деками, в которых записаны целочисленные данные. Ввести контроля (вывода) текущего состояния противня. Предусмотреть недопустимости ошибок при некорректных... https://www.cyberforum.ru/ cpp-beginners/ thread2828506.html
Проверить правильность скобочной последовательности используя стек C++
3. Будем рассматривать последовательности круглых и квадратных скобок, которые открываются и и закрываются () . Среди всех таких последовательностей выделим правильные - те, которые могут быть...
C++ Создать и распечатать два стека - с четными и нечетными числами 2. Создать и распечатать два стека - с четными и нечетными числами среди введенных. https://www.cyberforum.ru/ cpp-beginners/ thread2828504.html
C++ Введение в стек целых чисел с клавиатуры https://www.cyberforum.ru/ cpp-beginners/ thread2828503.html
1. Написать программу, которая предусматривает введение в стек целых чисел с клавиатуры. Вывести стек на экран. Какой порядок следования чисел?
C++ Изменение регистра символа
4. Разработать программу. Задание. Написать программу, которая в цикле преобразует введенный строчный символ на прописной и наоборот, условие завершения цикла - символ <.>. Конечный результат на...
C++ Поиск введенного с клавиатуры символа в строке https://www.cyberforum.ru/ cpp-beginners/ thread2828501.html
3. Разработать программу. Задание. Написать программу, которая будет осуществлять поиск введенного с клавиатуры символа, в некоторой строке, ранее введенной с клавиатуры. Конечный результат на...
C++ Добавить массив в файл Всем сап, есть задание, добавить массив в файл, который будет создаваться сам. Но есть проблема, он записывается не один раз и не могу понять, с чем это связано, буду рад любой помощи и заранее... https://www.cyberforum.ru/ cpp-beginners/ thread2828500.html
Быстрый линейный поиск C++
Подскажите что такое быстрый линейный поиск и чем он отличается от линейного Линейный поиск int searchPos(int* arr, int n, int search) { int index = -1; for (int i = 0; i < n; i++) ...
C++ Как ограничить количество введения переменных? https://www.cyberforum.ru/ cpp-beginners/ thread2828491.html
У меня есть код, в котором я ввожу и сохраняю текст в файл. Но у меня вводится бесконечное количество строк, как это исправить(переменная v)? #include <iostream> #include <string> #include...
0 / 0 / 0
Регистрация: 13.09.2020
Сообщений: 89
0

Алгоритм АВЛ-Деревьев - C++ - Ответ 15486083

12.05.2021, 11:58. Показов 218. Ответов 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;
}
Пишет, переполнение, но не понимаю, почему

Вернуться к обсуждению:
Алгоритм АВЛ-Деревьев C++
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.05.2021, 11:58
Помогаю со студенческими работами здесь

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

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

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

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

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

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

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