Pohon AVL di C++
Pohon AVL merupakan jenis pohon pencarian biner seimbang yang dikembangkan oleh Georgy Adelson-Velsky dan Evgenii Landis pada tahun 1962. Pohon AVL menjamin bahwa tinggi pohon tetap seimbang dengan memutar node ketika diperlukan, sehingga operasi pencarian, penyisipan, dan penghapusan dapat dilakukan dengan kompleksitas waktu logaritmik.
Keuntungan Pohon AVL
- Pencarian yang lebih cepat: Karena pohon AVL seimbang, pencarian elemen dapat dilakukan dengan kompleksitas waktu logaritmik, lebih cepat daripada pohon pencarian biner biasa yang dapat memiliki kompleksitas waktu linear dalam kasus terburuk.
- Penyisipan dan penghapusan yang efisien: Operasi penyisipan dan penghapusan pada pohon AVL juga memiliki kompleksitas waktu logaritmik, menjaga keseimbangan pohon dan efisiensi operasi.
- Kompleksitas ruang logaritmik: Pohon AVL memiliki kompleksitas ruang logaritmik, sehingga cocok untuk menyimpan dataset besar.
Implementasi Pohon AVL di C++
Berikut adalah contoh implementasi pohon AVL di C++:
#include
// Struktur Node AVL
struct Node {
int data;
int height;
Node *left;
Node *right;
Node(int data) {
this->data = data;
this->height = 1;
this->left = this->right = nullptr;
}
};
// Fungsi untuk menghitung tinggi node
int height(Node *node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
// Fungsi untuk menghitung faktor keseimbangan node
int getBalance(Node *node) {
if (node == nullptr) {
return 0;
}
return height(node->left) - height(node->right);
}
// Fungsi untuk melakukan rotasi kanan pada node
Node* rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;
// Lakukan rotasi
x->right = y;
y->left = T2;
// Perbarui tinggi
y->height = std::max(height(y->left), height(y->right)) + 1;
x->height = std::max(height(x->left), height(x->right)) + 1;
// Kembalikan node baru
return x;
}
// Fungsi untuk melakukan rotasi kiri pada node
Node* leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;
// Lakukan rotasi
y->left = x;
x->right = T2;
// Perbarui tinggi
x->height = std::max(height(x->left), height(x->right)) + 1;
y->height = std::max(height(y->left), height(y->right)) + 1;
// Kembalikan node baru
return y;
}
// Fungsi untuk menyisipkan node baru ke dalam pohon AVL
Node* insert(Node *node, int data) {
// Jika pohon kosong, buat node baru
if (node == nullptr) {
return new Node(data);
}
// Rekursi untuk menemukan posisi penyisipan
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
} else {
return node; // Jika data sudah ada, kembalikan node yang ada
}
// Perbarui tinggi node saat ini
node->height = std::max(height(node->left), height(node->right)) + 1;
// Hitung faktor keseimbangan
int balance = getBalance(node);
// Rotasi untuk menjaga keseimbangan
// Kasus 1: Left Left
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
// Kasus 2: Right Right
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
// Kasus 3: Left Right
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Kasus 4: Right Left
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
// Kembalikan node yang diperbarui
return node;
}
// Fungsi utama
int main() {
Node *root = nullptr;
// Sisipkan beberapa node
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
// Cetak data pohon AVL
std::cout << "Pohon AVL:\n";
// ... (Fungsi untuk mencetak pohon AVL)
return 0;
}
Kode di atas menunjukkan implementasi dasar pohon AVL di C++, termasuk struktur node, fungsi perhitungan tinggi dan faktor keseimbangan, serta fungsi rotasi kiri dan kanan. Fungsi insert() bertanggung jawab untuk memasukkan node baru dan menjaga keseimbangan pohon AVL.
Kesimpulan
Pohon AVL merupakan struktur data yang efisien dan seimbang yang menawarkan keuntungan kinerja yang signifikan dalam operasi pencarian, penyisipan, dan penghapusan. Implementasi di C++ memberikan framework dasar untuk membangun dan memanipulasi pohon AVL, memungkinkan pengembang untuk memanfaatkan efisiensi dan keandalannya dalam berbagai aplikasi.