|
Bajardi: Nuriddinov Boburbek Takshirdi: Akbarova Marg’uba Mavzu: avl daraxti Reja
|
| bet | 6/6 | | Sana | 04.12.2023 | | Hajmi | 359,14 Kb. | | #110716 |
#include
#include
struct Node {
int data;
Node* left;
Node* right;
int height;
};
int height(Node* node) {
if (node == nullptr)
return 0;
return node->height;
}
int balanceFactor(Node* node) {
if (node == nullptr)
return 0;
return height(node->left) - height(node->right);
}
Node* rotateRight(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* rotateLeft(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* insert(Node* node, int data) {
if (node == nullptr) {
Node* newNode = new Node;
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
newNode->height = 1;
return newNode;
}
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
else
return node;
node->height = 1 + std::max(height(node->left), height(node->right));
int balance = balanceFactor(node);
if (balance > 1 && data < node->left->data)
return rotateRight(node);
if (balance < -1 && data > node->right->data)
return rotateLeft(node);
if (balance > 1 && data > node->left->data) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
if (balance < -1 && data < node->right->data) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
void preorderTraversal(Node* root) {
if (root == nullptr)
return;
std::cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
Node* root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
std::cout << "AVL Daraxti tushunchasi vaqtincha:\n";
preorderTraversal(root);
return 0;
}
Xulosa: Men bu mustaqil ishdan avl daraxati bo’yicha ko’plab ma’lumotlar oldim.
Foydalangan adabiyotlar:
Wirth N. Algoritmlar va ma'lumotlar tuzilmalari M.: Mir, 1989. 4.5-bob (272-286-betlar)
G. M. Adelson-Velskiy, E. M. Landis. Axborotni tashkil qilish uchun bitta algoritm // Doklady AN SSSR. 1962. V. 146, No 2. S. 263–266.
https://walker.uz/2020/10/16/balanced-search-tree-avl-tree/
https://robocontest.uz/tasks/1129
https://azkurs.org/
|
| |
