Avl Tree Implementation C++

7 min read Jul 03, 2024

Implementasi Pohon AVL dalam C++

Pohon AVL adalah struktur data pohon pencarian biner yang seimbang sendiri. Ini berarti bahwa untuk setiap node dalam pohon, tinggi subtree kiri dan kanan berbeda dengan paling banyak 1, sehingga memastikan bahwa pohon tetap seimbang dan operasi pencarian, penyisipan, dan penghapusan dapat dilakukan dalam waktu logaritmik.

Dalam artikel ini, kita akan menjelajahi implementasi pohon AVL dalam bahasa pemrograman C++.

Struktur Data

Pertama, kita perlu mendefinisikan struktur data untuk node pohon AVL. Setiap node akan berisi data, pointer ke anak kiri dan kanan, dan faktor keseimbangannya (BF). Faktor keseimbangan dihitung sebagai perbedaan tinggi antara subtree kanan dan kiri.

struct Node {
  int data;
  Node* left;
  Node* right;
  int bf; // Faktor Keseimbangan

  Node(int data) : data(data), left(nullptr), right(nullptr), bf(0) {}
};

Operasi Dasar

Berikut adalah operasi dasar yang diperlukan untuk mengimplementasikan pohon AVL:

1. Rotasi: Rotasi digunakan untuk menyeimbangkan kembali pohon ketika faktor keseimbangan node tertentu menjadi -2 atau 2. Ada empat jenis rotasi:

* **Rotasi Kanan (RR):** Melakukan rotasi kanan pada node yang memiliki faktor keseimbangan -2 dan anak kanannya memiliki faktor keseimbangan 1.
* **Rotasi Kiri (LL):** Melakukan rotasi kiri pada node yang memiliki faktor keseimbangan 2 dan anak kirinya memiliki faktor keseimbangan -1.
* **Rotasi Kanan-Kiri (RL):** Melakukan rotasi kanan pada anak kiri node dan kemudian rotasi kiri pada node itu sendiri. Ini digunakan ketika faktor keseimbangan node adalah -2 dan anak kanannya memiliki faktor keseimbangan -1.
* **Rotasi Kiri-Kanan (LR):** Melakukan rotasi kiri pada anak kanan node dan kemudian rotasi kanan pada node itu sendiri. Ini digunakan ketika faktor keseimbangan node adalah 2 dan anak kirinya memiliki faktor keseimbangan 1.

2. Tinggi: Fungsi height digunakan untuk menghitung tinggi subtree tertentu.

3. Faktor Keseimbangan: Fungsi getBalanceFactor digunakan untuk menghitung faktor keseimbangan node tertentu.

4. Penyisipan: Fungsi insert menyisipkan node baru ke dalam pohon. Saat menyisipkan, fungsi ini memperbarui faktor keseimbangan dan melakukan rotasi jika perlu untuk mempertahankan keseimbangan pohon.

5. Penghapusan: Fungsi remove menghapus node tertentu dari pohon. Seperti halnya penyisipan, fungsi ini memperbarui faktor keseimbangan dan melakukan rotasi jika perlu untuk mempertahankan keseimbangan pohon.

Implementasi C++

Berikut adalah implementasi C++ lengkap dari pohon AVL:

#include 

using namespace std;

struct Node {
  int data;
  Node* left;
  Node* right;
  int bf; // Faktor Keseimbangan

  Node(int data) : data(data), left(nullptr), right(nullptr), bf(0) {}
};

class AVLTree {
 public:
  Node* root;

  AVLTree() : root(nullptr) {}

  int height(Node* node) {
    if (node == nullptr) {
      return 0;
    }
    return 1 + max(height(node->left), height(node->right));
  }

  int getBalanceFactor(Node* node) {
    if (node == nullptr) {
      return 0;
    }
    return height(node->right) - height(node->left);
  }

  Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // Rotasi
    x->right = y;
    y->left = T2;

    // Perbarui faktor keseimbangan
    y->bf = getBalanceFactor(y);
    x->bf = getBalanceFactor(x);

    return x;
  }

  Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // Rotasi
    y->left = x;
    x->right = T2;

    // Perbarui faktor keseimbangan
    x->bf = getBalanceFactor(x);
    y->bf = getBalanceFactor(y);

    return y;
  }

  Node* insert(Node* node, int data) {
    if (node == nullptr) {
      return new Node(data);
    }

    if (data < node->data) {
      node->left = insert(node->left, data);
    } else if (data > node->data) {
      node->right = insert(node->right, data);
    } else {
      return node; // Data sudah ada
    }

    // Perbarui faktor keseimbangan node
    node->bf = getBalanceFactor(node);

    // Periksa apakah perlu melakukan rotasi
    if (node->bf > 1 && data > node->right->data) {
      return leftRotate(node);
    }

    if (node->bf < -1 && data < node->left->data) {
      return rightRotate(node);
    }

    if (node->bf > 1 && data < node->right->data) {
      node->right = rightRotate(node->right);
      return leftRotate(node);
    }

    if (node->bf < -1 && data > node->left->data) {
      node->left = leftRotate(node->left);
      return rightRotate(node);
    }

    return node;
  }

  void insert(int data) {
    root = insert(root, data);
  }

  // ... (fungsi penghapusan, pencarian, dll.)
};

int main() {
  AVLTree tree;

  tree.insert(10);
  tree.insert(20);
  tree.insert(30);
  tree.insert(40);
  tree.insert(50);
  tree.insert(25);

  cout << "Pohon AVL telah dibuat." << endl;

  return 0;
}

Kesimpulan

Implementasi pohon AVL dalam C++ memungkinkan kita untuk membuat struktur data yang seimbang sendiri, yang meningkatkan efisiensi operasi pencarian, penyisipan, dan penghapusan. Implementasi ini menggunakan fungsi rotasi untuk menjaga keseimbangan pohon dan memastikan kinerja logaritmik. Meskipun pohon AVL mungkin tampak kompleks pada awalnya, implementasinya cukup sederhana dan dapat digunakan untuk berbagai aplikasi.