#include <iostream> #include <algorithm> struct Node { int data; int left; int right;…
- User
#include #include
struct Node { int data; int left; int right; int height; };
int Height(int index, Node arr[]) { if (index == -1) return 0; if (arr[index].height > 0) return arr[index].height;
arr[index].height = 1 + std::max(Height(arr[index].left, arr), Height(arr[index].right, arr)); return arr[index].height; }
int Balance(int index, Node arr[]) { if (index == -1) return 0; return Height(arr[index].right, arr) - Height(arr[index].left, arr); }
void UpdateHeight(int index, Node arr[]) { if (index == -1) return;
arr[index].height = 1 + std::max(Height(arr[index].left, arr), Height(arr[index].right, arr)); }
int RightRotate(int y, Node arr[]) { int x = arr[y].left; int T2 = arr[x].right;
arr[x].right = y; arr[y].left = T2;
UpdateHeight(y, arr); UpdateHeight(x, arr);
return x; }
int LeftRotate(int x, Node arr[]) { int y = arr[x].right; int T2 = arr[y].left;
arr[y].left = x; arr[x].right = T2;
UpdateHeight(x, arr); UpdateHeight(y, arr);
return y; }
void print(int root, Node arr[]) { static int index = 4;
std::cout << arr[arr[root].left].data << ' '; std::cout << (arr[arr[root].left].left == -1 ? 0 : index) << ' '; ++index; std::cout << (arr[arr[root].left].left == -1 ? 0 : index) << '\n'; ++index;
std::cout << arr[arr[root].right].data << ' '; std::cout << (arr[arr[root].right].right == -1 ? 0 : index) << ' '; ++index; std::cout << (arr[arr[root].right].right == -1 ? 0 : index) << '\n'; ++index;
if (arr[arr[root].left].left != -1) { print(arr[root].left, arr); } if (arr[arr[root].right].right != -1) { print(arr[root].right, arr); } }
int main() { int n; std::cin >> n;
Node arr[n]; for (int i = 0; i < n; ++i) { std::cin >> arr[i].data; std::cin >> arr[i].left >> arr[i].right; arr[i].left -= 1; arr[i].right -= 1; arr[i].height = 0; }
for (int i = 0; i < n; ++i) { Height(i, arr); }
int root = 0; if (Balance(arr[root].right, arr) < 0) { arr[root].right = RightRotate(arr[root].right, arr); }
root = LeftRotate(root, arr);
std::cout << n << std::endl; std::cout << root << ' ' << 2 << ' ' << 3 << '\n'; print(root, arr);
return 0; }
3
3 0 2 5 1 0 4 0 0 [1] 57470 segmentation fault ./mainисправь(сам принцип выводо с index измнениться не должен)
- Assistant
Программа выдает ошибку «сегментации фолт» из-за обращения к недопустимой памяти. В данном коде есть несколько моментов, которые могут привести к этому:
- Индекс
indexв функцииprintявляется статической переменной, и увеличивается при каждом вызовеprint. При последующих вызовахprint, начальное значение индекса продолжит увеличиваться, и это может привести к выходу за пределы массива нод, или вывод некорректных индексов. - Входные данные предполагают, что индексы детей начинаются с
1,0означает отсутствие ребенка, но в коде они изменяются на-1дляleftиright, и следует быть очень осторожным, чтобы не обратиться к массивуarrс недействительным индексом.
Если исправить код так, чтобы он корректно работал с индексами и надежно выводил дерево, результат будет выглядеть примерно так:
#include <iostream> #include <algorithm> struct Node { int data; int left; // these are the 1-based input indices as provided int right; // these are the 1-based input indices as provided int height; }; int Height(int index, Node arr[]) { if (index <= 0) return 0; // modified to handle 1-based indices instead of -1 index--; // adjust for 0-based indexing within the function if (arr[index].height > 0) return arr[index].height; arr[index].height = 1 + std::max(Height(arr[index].left, arr), Height(arr[index].right, arr)); return arr[index].height; } int Balance(int index, Node arr[]) { if (index <= 0) return 0; // modified to handle 1-based indices index--; // adjust for 0-based indexing within the function return Height(arr[index].right, arr) - Height(arr[index].left, arr); } void UpdateHeight(int index, Node arr[]) { if (index <= 0) return; // modified to handle 1-based indices index--; // adjust for 0-based indexing within the function arr[index].height = 1 + std::max(Height(arr[index].left, arr), Height(arr[index].right, arr)); } int RightRotate(int y, Node arr[]) { y--; // adjust for 0-based indexing int x = arr[y].left - 1; int T2 = arr[x].right; arr[x].right = y + 1; // revert to 1-based index after internal processing arr[y].left = T2; UpdateHeight(y + 1, arr); UpdateHeight(x + 1, arr); return x + 1; // return as 1-based index for internal processing } int LeftRotate(int x, Node arr[]) { x--; // adjust for 0-based indexing int y = arr[x].right - 1; int T2 = arr[y].left; arr[y].left = x + 1; // revert to 1-based index after internal processing arr[x].right = T2; UpdateHeight(x + 1, arr); UpdateHeight(y + 1, arr); return y + 1; // return as 1-based index for internal processing } void print(int root, Node arr[], int &index) { if (root <= 0) return; root--; // adjust for 0-based indexing if (arr[root].left > 0) { std::cout << arr[root].data << ' '; std::cout << arr[root].left << ' '; std::cout << "0\n"; print(arr[root].left, arr, ++index); // Need to pass index by reference } if (arr[root].right > 0) { std::cout << arr[root].data << ' '; std::cout << "0" << ' '; std::cout << arr[root].right << '\n'; print(arr[root].right, arr, ++index); // Need to pass index by reference } } int main() { int n; std::cin >> n; Node arr[n]; for (int i = 0; i < n; ++i) { std::cin >> arr[i].data; std::cin >> arr[i].left >> arr[i].right; arr[i].height = 0; } for (int i = 0; i < n; ++i) { Height(i + 1, arr); // pass 1-based index for root } int root = 1; // start with 1-based index for root if (Balance(arr[root].right, arr) < 0) { arr[root].right = RightRotate(arr[root].right, arr); } root = LeftRotate(root, arr); std::cout << n << std::endl; int index = 1; // Initialize index for proper printing print(root, arr, index); // Pass index by reference return 0; }Обратите внимание, что я убрал статическую переменную
indexиз функцииprintи передаю ее в функции как аргумент, чтобы избежать проблем с индексацией между вызовами. Я также изменил индексы для работы с 1-базированным входными данными в соответствии с тем, как они управляются внутри структурыNode. - Индекс
- User
#include
struct Node { int data; int height; Node* left; Node* right; };
struct NedoNode { int data; int left; int right; };
Node* ReCalculateHeight(Node* root) {
}
Node* BuildTree(Node* root, NedoNode arr[]) { if (root == nullptr) { root->data = arr[0].data; }
if (arr[root->data].left != -1) { Node* left_node = new Node; left_node->data = arr[arr[root->data].left].data; root->left = left_node; BuildTree(left_node, arr); }
if (arr[root->data].right != -1) { Node* right_node = new Node; right_node->data = arr[arr[root->data].right].data; root->right = right_node; BuildTree(right_node, arr); }
return root; }
Node* LeftRotation(Node* root) { Node *y = x->right;
Node *T2 = y->left;// Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; // Return new root return y;}
Node* RightRotation(Node* root) { Node *x = y->left;
Node *T2 = x->right;x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x;}
int main() { int n; int data; int left; int right; std::cin >> n;
NedoNode arr[n];
for (int i = 0; i < n; ++i) { std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; arr[i].right = right - 1; }
}
напиши RecalulateHeight
- Assistant
In the function
ReCalculateHeight, you'll traverse the tree in a post-order manner (left child, right child, then the node itself) to update each node's height. To calculate the height of a node, you need to look at the heights of its left and right children, take the larger one, and then add one.Here's an implementation for
ReCalculateHeight:#include <algorithm> // for std::max // Helper function to get the height of a node, handling null pointers. int height(Node* node) { if (node == nullptr) { return 0; // The height of a non-existent node is 0. } return node->height; } // The main `ReCalculateHeight` function which updates the height of each node. Node* ReCalculateHeight(Node* root) { if (root == nullptr) { return nullptr; // If the node is null, just return null. } // First, calculate the height of the left and right subtrees. root->left = ReCalculateHeight(root->left); root->right = ReCalculateHeight(root->right); // Then, update the height of the current node. The height is the max height of // the two children, plus 1 for the current node's level. root->height = 1 + std::max(height(root->left), height(root->right)); return root; // Return the node after its height has been updated. }Remember, the
heightfunction is a helper that returns the height of the node and handles null pointers by returning0.ReCalculateHeightthen takes care of the recursive traversal and height updates.You need to have
#include <algorithm>at the top of your code file to usestd::max. - User
#include
struct Node { int data; int height; Node* left; Node* right; };
struct NedoNode { int data; int left; int right; };
int height(Node *N) {
if (N == nullptr) return 0;
return N->height;
}Node* ReCalculateHeight(Node* root) { if (root == nullptr) { return nullptr; }
root->left = ReCalculateHeight(root->left); root->right = ReCalculateHeight(root->right);
root->height = 1 + std::max(height(root->left), height(root->right));
return root; }
Node* BuildTree(Node* root, NedoNode arr[]) { if (root == nullptr) { root->data = arr[0].data; }
if (arr[root->data].left != -1) { Node* left_node = new Node; left_node->data = arr[arr[root->data].left].data; root->left = left_node; BuildTree(left_node, arr); }
if (arr[root->data].right != -1) { Node* right_node = new Node; right_node->data = arr[arr[root->data].right].data; root->right = right_node; BuildTree(right_node, arr); }
return root; }
Node* LeftRotation(Node* x) { Node *y = x->right;
Node *T2 = y->left;y->left = x; x->right = T2; x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1; return y;}
Node* RightRotation(Node* y) { Node *x = y->left;
Node *T2 = x->right;x->right = y; y->left = T2; y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1; return x;}
int heights(Node* node) { if (node == NULL) return 0; else {
int lheight = heights(node->left); int rheight = heights(node->right); if (lheight > rheight) { return (lheight + 1); } else { return (rheight + 1); } }}
void printCurrentLevel(Node* root, int level) { if (root == NULL) return; if (level == 1) std::cout << root->data << " "; else if (level > 1) { printCurrentLevel(root->left, level - 1); printCurrentLevel(root->right, level - 1); } }
void printLevelOrder(Node* root) { int h = heights(root); int i; for (i = 1; i <= h; i++) printCurrentLevel(root, i); }
int main() { int n; int data; int left; int right; std::cin >> n;
NedoNode arr[n];
for (int i = 0; i < n; ++i) { std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; arr[i].right = right - 1; } Node* root; BuildTree(root, arr); printLevelOrder(root); }
7 -2 7 2 8 4 3 9 0 0 3 5 6 0 0 0 6 0 0 -7 0 0 [1] 60140 segmentation fault ./main
- Assistant
The segmentation fault you're encountering is due to attempting to access or modify a null pointer in your
BuildTreefunction. You must create a newNodebefore you start setting its data and children, but your current checkif (root == nullptr)does not make sense because you need to allocate memory for a new node first. Moreover, yourmainfunction does not initializerootbefore passing it toBuildTree.Here's a revised version of the
BuildTreefunction:Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0 || index >= n) { return nullptr; } Node* node = new Node; node->data = arr[index].data; node->left = BuildTree(arr, arr[index].left, n); node->right = BuildTree(arr, arr[index].right, n); node->height = 1 + std::max(height(node->left), height(node->right)); return node; }And the fixed
mainfunction that initializesrootproperly:int main() { int n; std::cin >> n; NedoNode arr[n]; for (int i = 0; i < n; ++i) { int data, left, right; std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; // Convert to 0-based index arr[i].right = right - 1; // Convert to 0-based index } Node* root = BuildTree(arr, 0, n); // Start building tree from index 0 printLevelOrder(root); // Don't forget to delete the nodes to prevent memory leaks return 0; }In this version,
BuildTreeis a standalone function that does not rely on a pre-existingrootnode. It creates the tree recursively by allocating new nodes as it goes. This function now also accepts the array ofNedoNodestructures, the current index for creating aNode, and the size of the array (n) to prevent indexing out of bounds.Also, in
main, therootvariable is now initialized with the return value fromBuildTree.Remember that every time you call
newto allocate memory for a node, you should also have a correspondingdeleteto deallocate this memory to prevent memory leaks. You will need to write a cleanup function to traverse the tree anddeleteeach node after you are done using it. - User
#include
struct Node { int data; int height; Node* left; Node* right; };
struct NedoNode { int data; int left; int right; };
int height(Node *N) {
if (N == nullptr) return 0;
return N->height;
}Node* ReCalculateHeight(Node* root) { if (root == nullptr) { return nullptr; }
root->left = ReCalculateHeight(root->left); root->right = ReCalculateHeight(root->right);
root->height = 1 + std::max(height(root->left), height(root->right));
return root; }
Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0 || index >= n) { return nullptr; }
Node* node = new Node; node->data = arr[index].data; node->left = BuildTree(arr, arr[index].left, n); node->right = BuildTree(arr, arr[index].right, n); node->height = 1 + std::max(height(node->left), height(node->right));
return node; }
Node* LeftRotation(Node* x) { Node *y = x->right;
Node *T2 = y->left;y->left = x; x->right = T2; x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1; return y;}
Node* RightRotation(Node* y) { Node *x = y->left;
Node *T2 = x->right;x->right = y; y->left = T2; y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1; return x;}
int heights(Node* node) { if (node == NULL) return 0; else {
int lheight = heights(node->left); int rheight = heights(node->right); if (lheight > rheight) { return (lheight + 1); } else { return (rheight + 1); } }}
void printCurrentLevel(Node* root, int level, int& counter_childs) { if (root == nullptr) return; if (level == 1) {
std::cout << root->data; if (root->left != nullptr) { std::cout << ' ' << ++counter_childs; } else { std::cout << ' ' << 0; } if (root->right != nullptr) { std::cout << ' ' << ++counter_childs; } else { std::cout << ' ' << 0; } std::cout << '\n'; } else if (level > 1) { printCurrentLevel(root->left, level - 1, counter_childs); printCurrentLevel(root->right, level - 1, counter_childs); }}
void printLevelOrder(Node* root) { int counter_childs = 1; int h = heights(root); int i; for (i = 1; i <= h; i++) printCurrentLevel(root, i, counter_childs); }
int main() { int n; int data; int left; int right; std::cin >> n;
NedoNode arr[n];
for (int i = 0; i < n; ++i) { std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; arr[i].right = right - 1; } Node* root; root = BuildTree(arr, 0, n); root->right = RightRotation(root->right); root = LeftRotation(root); std::cout << n; printLevelOrder(root); }
можны ли заменить heights на height?
- Assistant
Yes, you can use the
heightfunction to replace the purpose of theheightsfunction, but you will need to adjust theprintLevelOrderandprintCurrentLevelfunctions to use it properly.Here's how you can modify the code:
- Remove the
heightsfunction as it's essentially doing the same thing as theheightfunction but in a more complicated way. - Modify the
printLevelOrderfunction to use theheightfunction to get the height of the tree. - Adjust
printCurrentLevelto not take the height fromheights.
Here's the updated code:
// ... void printCurrentLevel(Node* root, int level, int& counter_childs) { if (root == nullptr) return; if (level == 1) { // ... // Print children or zeroes. // ... } else if (level > 1) { printCurrentLevel(root->left, level - 1, counter_childs); printCurrentLevel(root->right, level - 1, counter_childs); } } void printLevelOrder(Node* root) { int h = height(root); // Use the existing height function to determine tree height int counter_childs = 1; // Initialize counter for child nodes at 1 for (int i = 1; i <= h; i++) { printCurrentLevel(root, i, counter_childs); } } // ...This change is simply replacing the
heightsfunction calls withheight, which accomplishes the same effect. Theheightfunction now does double duty; it is used both to set the height of a node after any rotation operations in the AVL tree and to determine the height of the tree for level-order printing.In summary, you can use
heightinstead ofheightswith the proper adjustment toprintLevelOrder. Make sure after rotations (as they are in yourLeftRotationandRightRotationfunctions) that theheightof the affected nodes, as well as their parents, grandparents, etc., is properly updated. This is necessary to ensure that you can properly compute the level of the tree inprintLevelOrder. - Remove the
- User
#include
struct Node { int data; int height; Node* left; Node* right; };
struct NedoNode { int data; int left; int right; };
int height(Node *N) {
if (N == nullptr) return 0;
return N->height;
}Node* ReCalculateHeight(Node* root) { if (root == nullptr) { return nullptr; }
root->left = ReCalculateHeight(root->left); root->right = ReCalculateHeight(root->right);
root->height = 1 + std::max(height(root->left), height(root->right));
return root; }
Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0 || index >= n) { return nullptr; }
Node* node = new Node; node->data = arr[index].data; node->left = BuildTree(arr, arr[index].left, n); node->right = BuildTree(arr, arr[index].right, n); node->height = 1 + std::max(height(node->left), height(node->right));
return node; }
Node* LeftRotation(Node* x) { Node *y = x->right;
Node *T2 = y->left;y->left = x; x->right = T2; x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1; return y;}
Node* RightRotation(Node* y) { Node *x = y->left;
Node *T2 = x->right;x->right = y; y->left = T2; y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1; return x;}
int heights(Node* node) { if (node == NULL) return 0; else {
int lheight = heights(node->left); int rheight = heights(node->right); if (lheight > rheight) { return (lheight + 1); } else { return (rheight + 1); } }}
void PrintCurrentLevel(Node* root, int level, int& counter_childs, int& index, NedoNode arr[]) { if (root == nullptr) return; if (level == 1) { arr[index].data = root->data; if (root->left != nullptr) { arr[index].left = ++counter_childs; } else { arr[index].left = 0; } if (root->right != nullptr) { arr[index].right = ++counter_childs; } else { arr[index].right = 0; } ++index; } else if (level > 1) { PrintCurrentLevel(root->left, level - 1, counter_childs, index, arr); PrintCurrentLevel(root->right, level - 1, counter_childs, index, arr); } }
void PrintLevelOrder(Node* root, NedoNode arr[]) { int h = height(root); int counter_childs = 1; int index = 0; for (int i = 1; i <= h; i++) { PrintCurrentLevel(root, i, counter_childs, index, arr); } }
int main() { int n; int data; int left; int right; std::cin >> n;
NedoNode arr[n];
for (int i = 0; i < n; ++i) { std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; arr[i].right = right - 1; } Node* root; root = BuildTree(arr, 0, n); root->right = RightRotation(root->right); root = LeftRotation(root); std::cout << n << '\n'; PrintLevelOrder(root, arr);
for (int i = 0; i < n; ++i) { std::cout << arr[i].data << ' '; std::cout << arr[i].left << ' '; std::cout << arr[i].right << '\n'; } }
ошибка неправильнай формат вывода, почему, вот задача Для балансировки АВЛ-дерева при операциях вставки и удаления производятся левые и правые повороты. Левый поворот в вершине производится, когда баланс этой вершины больше 1, аналогично, правый поворот производится при балансе, меньшем 1.
Существует два разных левых (как, разумеется, и правых) поворота: большой и малый левый поворот.
Малый левый поворот осуществляется следующим образом:
{скоро тут будет иллюстрация}
Заметим, что если до выполнения малого левого поворота был нарушен баланс только корня дерева, то после его выполнения все вершины становятся сбалансированными, за исключением случая, когда у правого ребенка корня баланс до поворота равен 1. В этом случае вместо малого левого поворота выполняется большой левый поворот, который осуществляется так:
{скоро тут будет иллюстрация}
Дано дерево, в котором баланс дерева равен 2. Сделайте левый поворот.
Входные данные
Входные данные содержат описание двоичного дерева.
В первой строке файла находится число � n ( 1 ≤ � ≤ 2 ⋅ 1 0 5 1≤n≤2⋅10 5 ) - число вершин в дереве. В последующих � n строках файла находятся описания вершин дерева. В ( � + 1 i+1)-ой строке айла ( 1 ≤ � ≤ � 1≤i≤n) находится описание � i-ой вершины, состоящее из трех чисел � � K i , � � L i , � � R i , разделенных пробелами ключа в � i-ой вершине ( ∣ � � ∣ <
1 0 9 ∣Ki∣<=10 9 ), номера левого ребенка � i-ой вершины ( � < � � ≤ � i<L i ≤n или � �
0 L i =0, если левого ребенка нет) и номера правого ребенка � i-ой вершины ( � < � � ≤ � i<R i ≤n или � �
0 R i =0, если правого ребенка нет).
Все ключи различны. Гарантируется, что данное дерево является деревом поиска. Все ключи различны. Баланс корня дерева (вершины с номером 1) равен 2, баланс всех остальных вершин находится в пределах от -1 до 1.
Выходные данные
Выведите в том же формате дерево после осуществления левого поворота. Нумерация вершин может быть произвольной при условии соблюдения формата. Так, номер вершины должен быть меньше номера ее детей.
прмерр ввода 7 -2 7 2 8 4 3 9 0 0 3 5 6 0 0 0 6 0 0 -7 0 0 вывод 7 3 2 3 -2 4 5 8 6 7 -7 0 0 0 0 0 6 0 0 9 0 0
- Assistant
Давайте исправим выходной формат, чтобы он соответствовал требованиям задачи. Важно помнить, что в задаче номера узлов во входных данных начинаются с
1, а не с0, поэтому нужно увеличивать их на1при чтении и воссоздании дерева. Ваша текущая реализация также изменяет номера вершин при поворотах, что делает сложным восстановление исходной нумерации.Перепишем функции так, чтобы номера вершин оставались согласно формату ввода:
- В функции
BuildTreeсохраним оригинальные индексы вершин, а не их значения, для отслеживания связей между родителями и детьми. - Будем выводить информацию о вершинах дерева в соответствии с принципами АВЛ-деревьев.
Вот исправленный фрагмент кода:
Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0) { return nullptr; } Node* node = new Node; // Сохраняем индекс, а не значение, чтобы дети ссылались на исходные номера вершин node->data = index + 1; node->left = BuildTree(arr, arr[index].left - 1, n); node->right = BuildTree(arr, arr[index].right - 1, n); // Сначала выставляем высоту в 0, затем пересчитаем после создания всего дерева node->height = 0; return node; } void PrintInOrder(Node* node, NedoNode arr[]) { if (!node) return; int index = node->data - 1; // Возвращаемся к 0-базированному индексу для доступа к массиву if (node->left) arr[index].left = node->left->data; if (node->right) arr[index].right = node->right->data; PrintInOrder(node->left, arr); PrintInOrder(node->right, arr); } // ... int main() { // Считывание данных, предполагаем, что ввод корректный // ... // Строим дерево с нулевыми высотами Node* root = BuildTree(arr, 0, n); // Пересчет высот для всего дерева root = ReCalculateHeight(root); // Проверяем необходимость большого поворота if (height(root->right->left) > height(root->right->right)) { root->right = RightRotation(root->right); } root = LeftRotation(root); // Печать выходных данных std::cout << n << '\n'; // Инициализация всех left и right в arr как 0 для правильной печати for (int i = 0; i < n; ++i) { arr[i].left = 0; arr[i].right = 0; } // Выполняем "инверсию" операции BuildTree, чтобы каждая вершина ссылались на своих детей PrintInOrder(root, arr); // Печатаем результат в соответствии с заданием for (int i = 0; i < n; ++i) { std::cout << arr[i].data << ' ' << arr[i].left << ' ' << arr[i].right << '\n'; } }Обратите внимание, что я добавил функцию
PrintInOrder, которая проходит по дереву и обновляет массивarrсо ссылками на номера детей. Индексы в массивеarrсоответствуют ключам вершин, уменьшенных на 1 (так как в массиве индексы 0-базированные), а функцияReCalculateHeightтеперь обновляет высоты после построения дерева.После выполнения операции поворота мы обновляем ссылки на детей, чтобы можно было распечатать новую структуру дерева в соответствии с требованиями задачи.
- В функции
- User
#include
struct Node { int data; int height; Node* left; Node* right; };
struct NedoNode { int data; int left; int right; };
int height(Node *N) {
if (N == nullptr) return 0;
return N->height;
}Node* ReCalculateHeight(Node* root) { if (root == nullptr) { return nullptr; }
root->left = ReCalculateHeight(root->left); root->right = ReCalculateHeight(root->right);
root->height = 1 + std::max(height(root->left), height(root->right));
return root; }
Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0 || index >= n) { return nullptr; }
Node* node = new Node; node->data = arr[index].data; node->left = BuildTree(arr, arr[index].left, n); node->right = BuildTree(arr, arr[index].right, n); node->height = 1 + std::max(height(node->left), height(node->right));
return node; }
Node* LeftRotation(Node* x) { Node *y = x->right;
Node *T2 = y->left;y->left = x; x->right = T2; x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1; return y;}
Node* RightRotation(Node* y) { Node *x = y->left;
Node *T2 = x->right;x->right = y; y->left = T2; y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1; return x;}
void PrintCurrentLevel(Node* root, int level, int& counter_childs, int& index, NedoNode arr[]) { if (root == nullptr) return; if (level == 1) { arr[index].data = root->data; if (root->left != nullptr) { arr[index].left = ++counter_childs; } else { arr[index].left = 0; } if (root->right != nullptr) { arr[index].right = ++counter_childs; } else { arr[index].right = 0; } ++index; } else if (level > 1) { PrintCurrentLevel(root->left, level - 1, counter_childs, index, arr); PrintCurrentLevel(root->right, level - 1, counter_childs, index, arr); } }
void PrintLevelOrder(Node* root, NedoNode arr[]) { int h = height(root); int counter_childs = 1; int index = 0; for (int i = 1; i <= h; i++) { PrintCurrentLevel(root, i, counter_childs, index, arr); } }
int main() { int n; int data; int left; int right; std::cin >> n;
NedoNode arr[n];
for (int i = 0; i < n; ++i) { std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; arr[i].right = right - 1; } int new_value; std::cin >> new_value;
Node* root; root = BuildTree(arr, 0, n);
if (height(root->right->left) > height(root->right->right)) { root->right = RightRotation(root->right); } root = LeftRotation(root);
std::cout << n + 1 << '\n';
PrintLevelOrder(root, arr); for (int i = 0; i < n; ++i) { std::cout << arr[i].data << ' '; std::cout << arr[i].left << ' '; std::cout << arr[i].right << '\n'; } }
при создании дерева мне нужно подсчитывать высоту
- Assistant
Yes, you are correct that in the creation of an AVL tree, you need to calculate the height of the nodes during the tree construction process, so that you can properly implement the balancing operations (like rotations). However, there's a mistake in your current code in the
BuildTreefunction. When you callBuildTree, you shouldn't immediately assign the height in the recursive calls, because the children's heights have not yet been determined. This is what theReCalculateHeightfunction is meant for: it traverses the constructed tree and calculates the correct heights of all nodes.Here's how you can adjust the
BuildTreeand associated functions:// The BuildTree function shouldn't calculate height at this point. Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0 || index >= n) { return nullptr; } Node* node = new Node; node->data = arr[index].data; // Build left and right subtrees recursively node->left = BuildTree(arr, arr[index].left, n); node->right = BuildTree(arr, arr[index].right, n); // Don't assign height here; it will be calculated later. node->height = 0; return node; } // After building the tree, you need to call ReCalculateHeight to set the correct heights for all nodes. root = ReCalculateHeight(root); // ... Rest of your code...Regarding the rotation functions, both
LeftRotationandRightRotationshould also update the height of the affected nodes. However, after a rotation, you only need to update the height of the nodes that were moved, not the entire tree. Your rotation functions are already updating the heights of the rotated nodes.In the
mainfunction, after you build the tree and before you perform rotations, callReCalculateHeight:// ... Previously entered code ... Node* root = BuildTree(arr, 0, n); // Now we calculate the height for the entire tree, which is required for balancing an AVL tree. root = ReCalculateHeight(root); // Performing rotations if necessary if (height(root->right->left) > height(root->right->right)) { root->right = RightRotation(root->right); } root = LeftRotation(root); // After rotations, recalculate the height for the entire tree to get updated heights. root = ReCalculateHeight(root); // Output and additional code...Finally, make sure that your
PrintLevelOrderfunction is correctly capturing and printing the tree structure in the format expected by the problem's specification. Currently, it looks like yourPrintCurrentLevelandPrintLevelOrderfunctions are not correctly building the output structure—your index calculation seems to be off, and you might be overwriting parent nodes with child nodes inarr. Instead, it may be a better approach to perform an in-order traversal and keep a running index of the nodes you visit, hence mapping the original tree structure directly to the output arrayarr. Make sure yourarrrefers to the correct children indices after all rotations have been performed, and remember to adjust for 1-based indexing. - User
#include
struct Node { int data; int height; Node* left; Node* right; };
struct NedoNode { int data; int left; int right; };
int height(Node *N) {
if (N == nullptr) return 0;
return N->height;
}Node* ReCalculateHeight(Node* root) { if (root == nullptr) { return nullptr; }
root->left = ReCalculateHeight(root->left); root->right = ReCalculateHeight(root->right);
root->height = 1 + std::max(height(root->left), height(root->right));
return root; }
Node* BuildTree(NedoNode arr[], int index, int n) { if (index < 0 || index >= n) { return nullptr; }
Node* node = new Node; node->data = arr[index].data; node->left = BuildTree(arr, arr[index].left, n); node->right = BuildTree(arr, arr[index].right, n); node->height = 1 + std::max(height(node->left), height(node->right));
return node; }
Node* LeftRotation(Node* x) { Node *y = x->right;
Node *T2 = y->left;y->left = x; x->right = T2; x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1; return y;}
Node* RightRotation(Node* y) { Node *x = y->left;
Node *T2 = x->right;x->right = y; y->left = T2; y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1; return x;}
int Balance(Node* root) { if (root == nullptr) return 0; return height(root->left) - height(root->right); }
Node* Insert(Node* root, int key) { if (root == nullptr) { root->data = key; return root; }
if (key < root->data) { root->left = Insert(root->left, key); } else if (key > root->data) { root->right = Insert(root->right, key); } else { return root; }
root->height = std::max(height(root->left), height(root->right)) + 1;
int balance = Balance(root);
if (balance > 1 && key < root->left->data) { return RightRotation(root); }
if (balance < -1 && key > root->right->data) { return LeftRotation(root); }
if (balance > 1 && key > root->left->data) { root->left = LeftRotation(root->left); return RightRotation(root); }
if (balance < -1 && key < root->right->data) { root->right = RightRotation(root->right); return LeftRotation(root); }
return root; }
void PrintCurrentLevel(Node* root, int level, int& counter_childs, int& index, NedoNode arr[]) { if (root == nullptr) return; if (level == 1) { arr[index].data = root->data; if (root->left != nullptr) { arr[index].left = ++counter_childs; } else { arr[index].left = 0; } if (root->right != nullptr) { arr[index].right = ++counter_childs; } else { arr[index].right = 0; } ++index; } else if (level > 1) { PrintCurrentLevel(root->left, level - 1, counter_childs, index, arr); PrintCurrentLevel(root->right, level - 1, counter_childs, index, arr); } }
void PrintLevelOrder(Node* root, NedoNode arr[]) { int h = height(root); int counter_childs = 1; int index = 0; for (int i = 1; i <= h; i++) { PrintCurrentLevel(root, i, counter_childs, index, arr); } }
int main() { int n; int data; int left; int right; std::cin >> n;
NedoNode arr[n + 1];
for (int i = 0; i < n; ++i) { std::cin >> data >> left >> right; arr[i].data = data; arr[i].left = left - 1; arr[i].right = right - 1; } int new_value; std::cin >> new_value;
Node* root; root = BuildTree(arr, 0, n);
if (height(root->right->left) > height(root->right->right)) { root->right = RightRotation(root->right); } root = LeftRotation(root);
std::cout << n + 1 << '\n';
PrintLevelOrder(root, arr); for (int i = 0; i < n + 1; ++i) { std::cout << arr[i].data << ' '; std::cout << arr[i].left << ' '; std::cout << arr[i].right << '\n'; } }
при таком тесте 2 3 0 2 4 0 0 5
вывод должен быть 3 4 2 3 3 0 0 5 0 0
исправь
- Assistant
Для корректной работы программы с указанным вводом и для того, чтобы получить ожидаемый вывод, необходимо исправить несколько моментов. А именно, необходимо исправить функцию
Insert, потому что в стартовом условии, когда корень равенnullptr, вы пытаетесь обратиться к полюdataуnullptr, что вызовет ошибку. Вам также надо убедиться, что добавляете новую вершину корректно.Исправим функцию
Insertследующим образом:Node* Insert(Node* root, int key) { // Правильно создаем новую вершину с заданным ключом if (root == nullptr) { Node* node = new Node; node->data = key; node->height = 1; // высота новой вершины node->left = nullptr; node->right = nullptr; return node; } // ... // Остальная часть функции остается неизменной }Следующая проблема заключается в функции
PrintLevelOrderиPrintCurrentLevel. ФункцияPrintLevelOrderдолжна проходить дерево и заполнять структуруNedoNodeпо порядку вершин, чтобы на выходе получить корректную нумерацию, идентичную исходной.Вам необходимо обходить дерево методом in-order или any-order и выводить данные с использованием индексов, которые содержат исходные отношения родителей и детей.
Вот пример того, как можно реализовать in-order обход для сохранения структуры дерева в массиве
arr:int index = 1; // Начальный индекс void InOrderTraversal(Node* node, NedoNode arr[], int& index) { if (node == nullptr) return; if (node->left != nullptr) { arr[index].left = index + 1; InOrderTraversal(node->left, arr, ++index); } else { arr[index].left = 0; } arr[index].data = node->data; if (node->right != nullptr) { arr[index].right = index + 1; InOrderTraversal(node->right, arr, ++index); } else { arr[index].right = 0; } } void PrintInOrder(Node* root, NedoNode arr[]) { if (root != nullptr) { InOrderTraversal(root, arr, index); } }Эта функция обходит дерево и заполняет
arr, сохраняя корректные связи. Индексindexиспользуется для отслеживания текущей позиции в массивеarr.Также, вам нужно добавить новую вершину с помощью функции
Insert:Node* root = BuildTree(arr, 0, n); root = ReCalculateHeight(root); // Вставляем новую вершину root = Insert(root, new_value); root = ReCalculateHeight(root); // Пересчитываем высоты после вставки PrintInOrder(root, arr);В функции
mainдля вывода вершин используйтеPrintInOrderвместоPrintLevelOrder. Вам также необходимо корректно обработать индексы, чтобы они соответствовали 1-based индексации.int main() { // Ваш код чтения данных... Node* root = BuildTree(arr, 0, n - 1); // n - 1 потому что используем 0-based индексацию root = Insert(root, new_value); // Вставка новой вершины // Инициализация всех left и right в arr как 0 for (int i = 1; i <= n; ++i) { arr[i].left = 0; arr[i].right = 0; } PrintInOrder(root, arr); // Заполнение массива arr std::cout << n + 1 << '\n'; for (int i = 1; i <= n + 1; ++i) { std::cout << arr[i].data << ' ' << arr[i].left << ' ' << arr[i].right << '\n'; } // Освобождение памяти, выделенной для дерева... return 0; }В этом фрагменте кода инициализируется
NedoNode arr[n + 1], чтобы иметь место для новой вершины, и используются корректные индексы. - User
#include #include
struct Node { std::string name; int count[3] = {0}; Node* left = nullptr; Node* right = nullptr;
Node(const std::string& name) : name(name) {} };
void Insert(Node*& root, const std::string& name, int student) { if (!root) { root = new Node(name); root->count[student]++; return; }
if (name < root->name) { Insert(root->left, name, student); } else if (name > root->name) { Insert(root->right, name, student); } else { root->count[student]++; } }
void CountScores(Node* node, int* scores) { if (!node) return;
CountScores(node->left, scores);
int studentsWithFile = node->count[0] + node->count[1] + node->count[2]; if (studentsWithFile == 1) { for (int i = 0; i < 3; ++i) { if (node->count[i] == 1) scores[i] += 3; } } else if (studentsWithFile == 2) { for (int i = 0; i < 3; ++i) { if (node->count[i] == 1) scores[i] += 1; } }
CountScores(node->right, scores); }
int main() { int n; std::cin >> n;
Node* root = nullptr; for (int j = 0; j < 3; ++j) { for (int i = 0; i < n; ++i) { std::string name; std::cin >> name; Insert(root, name, j); } }
int ans[3] = {0}; CountScores(root, ans);
for (int i = 0; i < 3; ++i) { std::cout << ans[i] << ' '; }
delete root; }
перепиши на авл дерево
- Assistant
Чтобы изменить структуру дерева с обычного бинарного дерева поиска на АВЛ (самобалансирующееся дерево), нам нужно ввести понятия баланса и поворотов (левый и правый) для поддержания сбалансированности дерева. Каждый узел будет также содержать информацию о своей высоте.
Ниже приведен переписанный код, включающий АВЛ-дерево:
#include <iostream> #include <string> #include <algorithm> struct Node { std::string name; int count[3] = {0}; Node* left = nullptr; Node* right = nullptr; int height = 1; // новое: высота узла для АВЛ-дерева Node(const std::string& name) : name(name) {} }; // Новая функция: получить высоту узла int getHeight(Node* N) { if (N == nullptr) return 0; return N->height; } // Новая функция: получить баланс узла int getBalance(Node* N) { if (N == nullptr) return 0; return getHeight(N->left) - getHeight(N->right); } // Новая функция: правый поворот Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1; x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1; return x; } // Новая функция: левый поворот Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1; y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1; return y; } // Обновленная функция: вставка в АВЛ-дерево void Insert(Node*& root, const std::string& name, int student) { if (!root) { root = new Node(name); root->count[student]++; return; } if (name < root->name) { Insert(root->left, name, student); } else if (name > root->name) { Insert(root->right, name, student); } else { root->count[student]++; } root->height = 1 + std::max(getHeight(root->left), getHeight(root->right)); int balance = getBalance(root); // Левый-левый (правый поворот) if (balance > 1 && name < root->left->name) { root = rightRotate(root); } // Правый-правый (левый поворот) else if (balance < -1 && name > root->right->name) { root = leftRotate(root); } // Левый-правый (двойной поворот) else if (balance > 1 && name > root->left->name) { root->left = leftRotate(root->left); root = rightRotate(root); } // Правый-левый (двойной поворот) else if (balance < -1 && name < root->right->name) { root->right = rightRotate(root->right); root = leftRotate(root); } } // Оставшиеся функции без изменений // ... int main() { // ... // Помните удалить каждый узел после использования, чтобы избежать утечек памяти deleteTree(root); }В этом коде я добавил новые функции для поддержания баланса в АВЛ-дереве:
getHeight,getBalance,rightRotate, иleftRotate. ФункцияInsertтеперь также включает логику балансировки после каждой вставки, выполняя повороты для сохранения свойств АВЛ-дерева. Функции подсчета балловCountScoresи основной код остаются без изменений.Не забудьте в конце освободить память, которая была выделена для каждого узла дерева, перебирая все узлы и освобождая их с помощью функции
delete. Необходимо создать функциюdeleteTree, которая будет обходить дерево и удалять каждый узел. - User
#include #include
struct Node { std::string name; int count[3] = {0}; Node* left = nullptr; Node* right = nullptr; int height = 1;
Node(const std::string& name) : name(name) {} };
int height(Node* root) { if (root == nullptr) return 0; return root->height; }
int Balance(Node* root) { if (root == nullptr) return 0; return height(root->left) - height(root->right); }
Node* RightRotation(Node* y) { Node* x = y->left; Node* T2 = x->right;
x->right = y; y->left = T2;
y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1;
return x; }
Node* LeftRotation(Node* x) { Node* y = x->right; Node* T2 = y->left;
y->left = x; x->right = T2;
x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1;
return y; }
void Insert(Node*& root, const std::string& name, int student) { if (!root) { root = new Node(name); root->count[student]++; return; }
if (name < root->name) { Insert(root->left, name, student); } else if (name > root->name) { Insert(root->right, name, student); } else { root->count[student]++; }
root->height = 1 + std::max(height(root->left), height(root->right));
int balance = Balance(root);
if (balance > 1 && name < root->left->name) { root = RightRotation(root); }
if (balance < -1 && name > root->right->name) { root = LeftRotation(root); }
if (balance > 1 && name > root->left->name) { root->left = LeftRotation(root->left); root = RightRotation(root); }
if (balance < -1 && name < root->right->name) { root->right = RightRotation(root->right); root = LeftRotation(root); } }
void CountScores(Node* node, int* scores) { if (!node) return;
CountScores(node->left, scores);
int studentsWithFile = node->count[0] + node->count[1] + node->count[2]; if (studentsWithFile == 1) { for (int i = 0; i < 3; ++i) { if (node->count[i] == 1) scores[i] += 3; } } else if (studentsWithFile == 2) { for (int i = 0; i < 3; ++i) { if (node->count[i] == 1) scores[i] += 1; } }
CountScores(node->right, scores); }
int main() { int n; std::cin >> n;
Node* root = nullptr; for (int j = 0; j < 3; ++j) { for (int i = 0; i < n; ++i) { std::string name; std::cin >> name; Insert(root, name, j); } }
int ans[3] = {0}; CountScores(root, ans);
for (int i = 0; i < 3; ++i) { std::cout << ans[i] << ' '; }
}
мой код не проходит 6-й тест этой задачи(я не знаю что это за тест) Три друга списывают лабораторную работу, каждый из них списывает по � n различных задач. Поскольку друзья не очень умные, они не меняют названия отправляемых на проверку файлов.
По истечении времени, отведенного на написание лабораторной, преподаватель запускает бан-машину и ставит баллы по следующим правилам:
если задача написана только у одного студента, то этот студент получает 3 балла, поскольку эту задачу он не списывал и не давал списывать; если задача списана ровно у двух студентов, то каждый из них получает по 1 утешительному баллу; если задача списана всеми тремя студентами, то за нее баллы не начисляются никому. Выведите финальное количество баллов у каждого студента.
В рамках этой задачи будем считать, что Бан-машина считает решения списанными, если у них полностью совпадают имена файлов.
Входные данные
В первой строке входных данных дается число � n ( 1 ≤ � ≤ 100000 1≤n≤100000) - количество задач в лабораторной.
Следующие три строки содержат по � n различных слов в каждой — названия файлов с решениями, отправленных каждым из студентов.
Выходные данные
Необходимо вывести 3 числа - количество баллов у первого, второго и третьего студента соответственно.
STDIN STDOUT 3 fir sec thi thi fir sec aaa sec bbb
2 2 6
Примечание
Решения, написанные при помощи сортировок, бинпоиска или встроенных деревьев не засчитываются. Set, Map и т.п. - запрещены.
вот правильная реализация на BST(но мне обязательно на авл)
#include #include
struct Node { std::string name; int count[3] = {0}; Node* left = nullptr; Node* right = nullptr;
Node(const std::string& name) : name(name) {} };
void Insert(Node*& root, const std::string& name, int student) { if (!root) { root = new Node(name); root->count[student]++; return; }
if (name < root->name) { Insert(root->left, name, student); } else if (name > root->name) { Insert(root->right, name, student); } else { root->count[student]++; } }
void CountScores(Node* node, int* scores) { if (!node) return;
CountScores(node->left, scores);
int studentsWithFile = node->count[0] + node->count[1] + node->count[2]; if (studentsWithFile == 1) { for (int i = 0; i < 3; ++i) { if (node->count[i] == 1) scores[i] += 3; } } else if (studentsWithFile == 2) { for (int i = 0; i < 3; ++i) { if (node->count[i] == 1) scores[i] += 1; } }
CountScores(node->right, scores); }
int main() { int n; std::cin >> n;
Node* root = nullptr; for (int j = 0; j < 3; ++j) { for (int i = 0; i < n; ++i) { std::string name; std::cin >> name; Insert(root, name, j); } }
int ans[3] = {0}; CountScores(root, ans);
for (int i = 0; i < 3; ++i) { std::cout << ans[i] << ' '; }
delete root; }
- Assistant
Ваш код АВЛ-дерева выглядит корректно; однако при использовании АВЛ-дерева важно правильно обновлять высоты узлов дерева и балансировать дерево после каждой вставки или удаления, чтобы гарантировать, что разница высот левого и правого поддеревьев никогда не превышает 1. Я заметил, что в вашей реализации вставки в АВЛ-дерево некоторые повороты выполняются без проверки условий баланса, что может приводить к неверной структуре дерева и, как следствие, некорректной работе программы на тестах.
Давайте уточним условия выполнения поворотов в функции
Insert:void Insert(Node*& root, const std::string& name, int student) { // ... Прочий код вставки остается неизменным ... // Повороты происходят только если высота поддерева нарушает баланс if (balance > 1 && name < root->left->name) { // Левый-левый случай root = RightRotation(root); return; } if (balance < -1 && name > root->right->name) { // Правый-правый случай root = LeftRotation(root); return; } if (balance > 1 && name > root->left->name) { // Левый-правый случай root->left = LeftRotation(root->left); root = RightRotation(root); return; } if (balance < -1 && name < root->right->name) { // Правый-левый случай root->right = RightRotation(root->right); root = LeftRotation(root); return; } }Дополнительно, вам нужно будет реализовать функцию, отвечающую за очистку памяти для всего дерева, а не просто удаление корня как
delete root. Правильная функция освобождения памяти должна рекурсивно проходить по всем узлам дерева и удалять их:void DeleteTree(Node* node) { if (!node) return; DeleteTree(node->left); DeleteTree(node->right); delete node; }Используйте эту функцию в
main, чтобы корректно освободить память:int main() { // ... Остальная часть функции main остается неизменной ... DeleteTree(root); }После внесения этих изменений программа должна корректно работать на всех тестах, сохраняя оптимальный баланс дерева за счет использования АВЛ-дерева.
- User
#include #include
struct Node { std::string name; int count[3] = {0}; Node* left = nullptr; Node* right = nullptr; int height = 1;
Node(const std::string& name) : name(name) {} };
int height(Node* root) { if (root == nullptr) return 0; return root->height; }
int Balance(Node* root) { if (root == nullptr) return 0; return height(root->left) - height(root->right); }
Node* RightRotation(Node* y) { Node* x = y->left; Node* T2 = x->right;
x->right = y; y->left = T2;
y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1;
return x; }
Node* LeftRotation(Node* x) { Node* y = x->right; Node* T2 = y->left;
y->left = x; x->right = T2;
x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1;
return y; }
void Insert(Node*& root, const std::string& name, int student, int& free_memory) { if (!root) { root = new Node(name); root->count[student]++; return; }
if (name < root->name) { Insert(root->left, name, student, free_memory); } else if (name > root->name) { Insert(root->right, name, student, free_memory); } else { free_memory += name.length(); }
root->height = 1 + std::max(height(root->left), height(root->right));
int balance = Balance(root);
if (balance > 1 && name < root->left->name) { root = RightRotation(root); } else if (balance < -1 && name > root->right->name) { root = LeftRotation(root); } else if (balance > 1 && name > root->left->name) { root->left = LeftRotation(root->left); root = RightRotation(root); } else if (balance < -1 && name < root->right->name) { root->right = RightRotation(root->right); root = LeftRotation(root); } }
int main() { int n; std::cin >> n; int free_memory = 0; Node* root = nullptr; for (int j = 0; j < n; ++j) { std::string name; std::cin >> name; Insert(root, name, j, free_memory); } std::cout << free_memory; }
почему то мое решение неправильное почему У Пети в телефоне записаны номера друзей. Однажды Петя заметил, что у него кончается свободная память на устройстве. Петя знал, что среди его контактов есть множество дубликатов. Он решил удалить повторяющиеся записи.
Каждый контакт - это строка, состоящая исключительно из строчных или заглавных букв латинского алфавита и цифр. При удалении строки освобождается � M байт памяти, где � M - количество различных символов в данной строке. Помогите Пете узнать, сколько памяти в байтах он сможет освободить.
Входные данные
В первой строке входных данных дается число � n ( 1 ≤ � ≤ 1 0 5 1≤n≤10 5 ) - количество контактов в телефоне.
В следующей строке записаны через пробел � n строк - контакты Пети.
Выходные данные
Выведите одно число - ответ на задачу.
пример ввода 5 qqwe qqwe abc s s вывод 4
Примечание
Решения, написанные при помощи сортировок, бинпоиска или встроенных деревьев, структур данных set, map и прочих - не засчитываются.
- Assistant
Из вашего описания видно, что задача состоит в удалении дубликатов контактов и подсчете освобожденной памяти. Освобождается количество байт памяти, равное количеству уникальных символов в каждой удаленной строке. У вас неправильное количество итераций во вложенных циклах в функции
mainпри вызове функцииInsert.Если каждый контакт списывается один раз, счетчик
jдолжен идти от0доnвключительно, а второй индекс в вызове функцииInsertдолжен всегда быть0, поскольку это не студенты, а дубликаты контактов.for (int j = 0; j < n; ++j) { std::string name; std::cin >> name; Insert(root, name, 0, free_memory); }Также в функции
Insertв веткеelse, которая выполняется при нахождении дубликата, вы удаляете длину строки из свободной памяти два раза, поэтомуfree_memoryполучает неверное значение. Это условие служит для подсчета количества удаленных дубликатов, что произойдет единожды для каждого дубликата. Также, нет необходимости в параметре student, так как у нас только один "студент" - Петя.Вам нужно просто увеличить
free_memoryна количество уникальных символов строки, что и будет количеством байт, освобождаемых при удалении контакта.Судя по всему, вам также необходимо реализовать корректное удаление всего дерева после его использования, чтобы освободить память, выделенную под узлы.
Корректированный код функции
Insertиmainбудет следующим:void Insert(Node*& root, const std::string& name, int& free_memory) { if (!root) { root = new Node(name); root->count[0]++; return; } if (name < root->name) { Insert(root->left, name, free_memory); } else if (name > root->name) { Insert(root->right, name, free_memory); } else { free_memory += name.length(); } // ... Обновление высоты узла и балансировка дерева остаются неизменными ... } int main() { int n; std::cin >> n; int free_memory = 0; Node* root = nullptr; for (int i = 0; i < n; ++i) { std::string name; std::cin >> name; Insert(root, name, free_memory); } std::cout << free_memory; // Не забываем удалить дерево DeleteTree(root); }И не забудьте реализовать функцию
DeleteTree()для освобождения памяти, как описано в предыдущем ответе:void DeleteTree(Node* node) { if (!node) return; DeleteTree(node->left); DeleteTree(node->right); delete node; }Теперь ваша программа должна правильно работать, подсчитывая освободившееся место в памяти и удаляя использованные ресурсы.
- User
#include #include
struct Node { std::string name; Node* left = nullptr; Node* right = nullptr; int height = 1;
Node(const std::string& name) : name(name) {} };
int height(Node* root) { if (root == nullptr) return 0; return root->height; }
int Balance(Node* root) { if (root == nullptr) return 0; return height(root->left) - height(root->right); }
Node* RightRotation(Node* y) { Node* x = y->left; Node* T2 = x->right;
x->right = y; y->left = T2;
y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1;
return x; }
Node* LeftRotation(Node* x) { Node* y = x->right; Node* T2 = y->left;
y->left = x; x->right = T2;
x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1;
return y; }
void Insert(Node*& root, const std::string& name, int& free_memory) { if (!root) { root = new Node(name); return; }
if (name < root->name) { Insert(root->left, name, free_memory); } else if (name > root->name) { Insert(root->right, name, free_memory); } else { free_memory += name.length(); }
root->height = 1 + std::max(height(root->left), height(root->right));
int balance = Balance(root);
if (balance > 1 && name < root->left->name) { root = RightRotation(root); } else if (balance < -1 && name > root->right->name) { root = LeftRotation(root); } else if (balance > 1 && name > root->left->name) { root->left = LeftRotation(root->left); root = RightRotation(root); } else if (balance < -1 && name < root->right->name) { root->right = RightRotation(root->right); root = LeftRotation(root); } }
int main() { int n; std::cin >> n; int free_memory = 0; Node* root = nullptr; for (int i = 0; i < n; ++j) { std::string name; std::cin >> name; Insert(root, name, free_memory); } std::cout << free_memory; }
исправь ошибку в мроей задаче(я имею ввиду условие про символы а не слова) У Пети в телефоне записаны номера друзей. Однажды Петя заметил, что у него кончается свободная память на устройстве. Петя знал, что среди его контактов есть множество дубликатов. Он решил удалить повторяющиеся записи.
Каждый контакт - это строка, состоящая исключительно из строчных или заглавных букв латинского алфавита и цифр. При удалении строки освобождается � M байт памяти, где � M - количество различных символов в данной строке. Помогите Пете узнать, сколько памяти в байтах он сможет освободить.
Входные данные
В первой строке входных данных дается число � n ( 1 ≤ � ≤ 1 0 5 1≤n≤10 5 ) - количество контактов в телефоне.
В следующей строке записаны через пробел � n строк - контакты Пети.
Выходные данные
Выведите одно число - ответ на задачу.
- Assistant
Итак, чтобы исправить ваш код, который учитывает количество различных символов в каждом контакте, а не просто длину, нам нужно изменить имплементацию параметра
free_memoryтак, чтобы он подсчитывал количество уникальных символов в строке, и это можно сделать с помощью стандартного контейнераstd::set, который позволит хранить только уникальные символы.Для эффективности решения не следует использовать
std::set, так как из условия задачи следует, что использование стандартных контейнеровset,mapи прочих не засчитывается. Поэтому мы можем определить уникальность символов, создав булев массив на основе ASCII значений символов (это быстрый и эффективный способ).Вот обновленный код функции
Insertиmainс учетом количества уникальных символов:#include <iostream> #include <string> #include <algorithm> // Остальные определения структуры Node и вспомогательных функций ... void Insert(Node*& root, const std::string& name, int& free_memory) { if (!root) { root = new Node(name); bool seen[128] = {false}; for (char c : name) { if (!seen[static_cast<unsigned char>(c)]) { free_memory++; seen[static_cast<unsigned char>(c)] = true; } } return; } if (name < root->name) { Insert(root->left, name, free_memory); } else if (name > root->name) { Insert(root->right, name, free_memory); } else { // Контакт с таким именем уже существует, дубликаты не добавляем } // Балансировка остается без изменений ... } int main() { int n; std::cin >> n; int free_memory = 0; Node* root = nullptr; for (int i = 0; i < n; ++i) { std::string name; std::cin >> name; Insert(root, name, free_memory); } std::cout << free_memory; // Здесь должен быть код для рекурсивного удаления дерева // DeleteTree(root); } // Функция DeleteTree должна быть реализована для корректного освобождения памяти.Также в вашем исходном коде есть опечатка в цикле
for, где вы используете переменнуюjвместоi:// ... for (int i = 0; i < n; ++j) { // ...Это должно быть исправлено на
i:for (int i = 0; i < n; ++i) { // ...Обратите внимание на то, что для работы с символами используется массив
seen, индексируемый по ASCII-значению символа. Мы предполагаем, что все символы — это печатаемые ASCII-символы, и их коды лежат в диапазоне от 0 до 127.Наконец, в конце программы должна быть добавлена функция
DeleteTreeдля удаления всех узлов дерева рекурсивным способом, чтобы избежать утечки памяти.