Faktor Keseimbangan pada Pohon AVL
Pohon AVL adalah jenis pohon pencarian biner yang seimbang sendiri, yang berarti bahwa untuk setiap simpul di pohon, perbedaan tinggi antara sub-pohon kiri dan kanannya tidak melebihi 1. Faktor keseimbangan di pohon AVL didefinisikan sebagai perbedaan tinggi antara sub-pohon kiri dan kanan.
Faktor Keseimbangan = Tinggi Sub-pohon Kanan - Tinggi Sub-pohon Kiri
Mengapa Faktor Keseimbangan Penting?
Faktor keseimbangan penting untuk menjaga pohon AVL seimbang. Jika faktor keseimbangan terlalu besar, pohon akan menjadi tidak seimbang dan akan membutuhkan waktu yang lama untuk mencari, memasukkan, atau menghapus simpul.
Cara Menghitung Faktor Keseimbangan
Faktor keseimbangan dapat dihitung dengan menggunakan fungsi rekursif. Fungsi ini akan menelusuri pohon dan menghitung tinggi sub-pohon kiri dan kanan untuk setiap simpul. Faktor keseimbangan kemudian dihitung sebagai selisih antara kedua tinggi tersebut.
Implementasi dalam C++
#include
using namespace std;
// Struktur simpul pohon AVL
struct Node {
int data;
int height;
Node *left;
Node *right;
};
// Fungsi untuk mendapatkan tinggi pohon
int height(Node *node) {
if (node == NULL) {
return 0;
}
return node->height;
}
// Fungsi untuk mendapatkan faktor keseimbangan pohon
int balanceFactor(Node *node) {
if (node == NULL) {
return 0;
}
return height(node->right) - height(node->left);
}
// Fungsi untuk membuat simpul baru
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->height = 1;
node->left = NULL;
node->right = NULL;
return node;
}
// Fungsi untuk melakukan rotasi kanan
Node* rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;
// Rotasi
x->right = y;
y->left = T2;
// Perbarui tinggi
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// Kembalikan simpul baru
return x;
}
// Fungsi untuk melakukan rotasi kiri
Node* leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;
// Rotasi
y->left = x;
x->right = T2;
// Perbarui tinggi
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// Kembalikan simpul baru
return y;
}
// Fungsi utama
int main() {
Node *root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
// Hitung faktor keseimbangan
cout << "Faktor Keseimbangan Root: " << balanceFactor(root) << endl;
return 0;
}
Kesimpulan
Faktor keseimbangan adalah konsep penting dalam pohon AVL. Ia membantu menjaga keseimbangan pohon, sehingga operasi pencarian, penyisipan, dan penghapusan dapat dilakukan secara efisien. Dengan memahami faktor keseimbangan, Anda dapat membangun dan menggunakan pohon AVL secara efektif dalam berbagai aplikasi.