Pohon AVL: Rotasi, Penyisipan, Penghapusan dengan C++ Example

Oleh: Sarah Chen Sarah Chen
Hours Updated

⚡ Ringkasan Cerdas

Pohon AVL adalah pohon pencarian biner yang menyeimbangkan diri sendiri di mana perbedaan tinggi antara subpohon kiri dan kanan setiap simpul tetap berada dalam rentang -1, 0, atau +1, sehingga menjamin kinerja pencarian O(log n).

  • 🌲 Definisi: Pohon pencarian biner di mana faktor keseimbangan setiap simpul terletak di {-1, 0, +1}, dinamai berdasarkan nama penemunya, Adelson-Velsky dan Landis.
  • ️ Faktor Keseimbangan: Dihitung sebagai tinggi(kiri) − tinggi(kanan); nilai di luar {-1, 0, +1} memicu rotasi untuk mengembalikan keseimbangan.
  • 🔄 Rotasi: Empat kasus — LL, RR, LR, dan RL — menyelaraskan kembali node setelah penyisipan atau penghapusan yang tidak seimbang untuk menjaga agar pohon tetap logaritmik dalam ketinggian.
  • ➕ Insersi: Penyisipan BST standar diikuti dengan pergerakan ke atas yang menghitung ulang faktor keseimbangan dan melakukan paling banyak satu atau dua rotasi tunggal.
  • ➖ Penghapusan: Sama seperti penghapusan BST tetapi dapat menyebabkan beberapa rotasi berjenjang ke atas pohon karena tinggi subpohon dapat menyusut di setiap leluhur.
  • 🚀 aplikasi: Basis data, indeks dalam memori, metadata sistem file, dan struktur pencarian AI menggunakan Pohon AVL untuk pencarian terurut yang cepat.
Baca Selengkapnya

Pohon AVL

Apa itu Pohon AVL?

Pohon AVL adalah pohon pencarian biner di mana perbedaan tinggi antara subpohon kiri dan kanan setiap simpul adalah -1, 0, atau +1. Pohon-pohon ini merupakan BST yang menyeimbangkan diri dan mempertahankan waktu pencarian logaritmik, dinamai berdasarkan penemunya, Adelson-Velsky dan Landis (AVL).

Bagaimana cara kerja Pohon AVL?

Untuk memahami mengapa AVL Tree ada, perhatikan apa yang salah dengan pohon biasa. Pohon Pencarian BinerPerhatikan kunci-kunci berikut yang dimasukkan dalam urutan yang diberikan:

Pekerjaan Pohon AVL

Visualisasi pohon AVL

Pohon tersebut tumbuh secara linear ketika kunci tiba dalam urutan meningkat, sehingga pencarian menjadi O(n). Hal itu menggagalkan tujuan BST — hanya pohon yang seimbang yang menjaga pencarian tetap logaritmik. Sekarang perhatikan kunci yang sama yang dimasukkan dalam urutan yang berbeda.

Pekerjaan Pohon AVL

Kunci yang sama, urutan penyisipan yang berbeda menghasilkan bentuk yang lebih dangkal, sehingga setiap pencarian berjalan dalam O(log n). Pohon AVL menerapkan bentuk tersebut dengan memantau ketinggian pada setiap penyisipan dan memperbaiki ketidakseimbangan tanpa merusak urutan BST.

Faktor Keseimbangan di Pohon AVL

Faktor keseimbangan (BF) tracks tinggi setiap node sehingga pohon dapat menyeimbangkan diri secara otomatis.

Sifat Faktor Keseimbangan

Faktor Keseimbangan di Pohon AVL

Faktor keseimbangan pohon AVL

  • Faktor keseimbangan adalah selisih antara tinggi subpohon kiri dan tinggi subpohon kanan.
  • Balance factor(node) = height(node->left) − height(node->right)
  • Nilai yang diperbolehkan hanyalah −1, 0, dan +1.
  • Nilai −1 berarti subpohon kanan berisi satu level tambahan — simpul tersebut berat di sebelah kanan.
  • Nilai +1 berarti subpohon kiri berisi satu level tambahan — simpul tersebut memiliki banyak level di sebelah kiri.
  • Nilai 0 berarti kedua sisi memiliki tinggi yang sama — simpul tersebut seimbang sempurna.

Rotasi AVL

Rotasi dijalankan setiap kali penyisipan atau penghapusan melanggar aturan faktor keseimbangan. Keempat kasus tersebut adalah LL, RR, LR, dan RL.

Kiri – Rotasi Kiri

Rotasi ini dilakukan ketika node baru disisipkan pada anak kiri dari subpohon kiri.

Pohon AVL Kiri – Rotasi Kiri

Pohon AVL Kiri – Rotasi Kiri

Rotasi kanan tunggal dilakukan. Kasus ini terjadi ketika sebuah node memiliki BF +2 dan anak kirinya memiliki BF +1.

Kanan – Rotasi Kanan

Rotasi ini dilakukan ketika node baru disisipkan pada anak kanan dari subpohon kanan.

Pohon AVL Kanan – Rotasi Kanan

Rotasi kiri tunggal dilakukan. Kasus ini terjadi ketika sebuah node memiliki BF −2 dan anak kanannya memiliki BF −1.

Rotasi Kanan – Kiri

Rotasi ini dilakukan ketika node baru disisipkan pada anak kiri dari subpohon kanan.

Pohon AVL Rotasi Kanan – Kiri

Terjadi ketika BF(node) = −2 dan BF(right-child) = +1. Putar anak kanan ke kanan, lalu putar node ke kiri.

Rotasi Kiri – Kanan

Rotasi ini dilakukan ketika node baru disisipkan pada anak kanan dari subpohon kiri.

Pohon AVL Rotasi Kiri – Kanan

Terjadi ketika BF(node) = +2 dan BF(left-child) = −1. Putar anak kiri ke kiri, lalu putar node ke kanan.

Penyisipan di Pohon AVL

Penyisipan hampir identik dengan penyisipan BST biasa. Setelah setiap penyisipan, pohon akan menelusuri ke atas dan menyeimbangkan kembali. Penyisipan berjalan dalam waktu O(log n) pada kasus terburuk.

Penyisipan di Pohon AVL

Implementasi penyisipan pohon AVL

Langkah 1: Masukkan node menggunakan algoritma BST standar. Pada contoh di atas, masukkan 160.

Langkah 2: Perbarui faktor keseimbangan setiap leluhur di sepanjang jalur penyisipan.

Langkah 3: Jika ada leluhur yang melanggar rentang faktor keseimbangan, lakukan rotasi yang sesuai. Dalam contoh ini, faktor keseimbangan node 350 dilanggar, sehingga rotasi LL mengembalikan keseimbangan.

  1. If BF(node) = +2 ke BF(left-child) = +1, lakukan rotasi LL.
  2. If BF(node) = −2 ke BF(right-child) = −1, lakukan rotasi RR.
  3. If BF(node) = −2 ke BF(right-child) = +1, lakukan rotasi RL.
  4. If BF(node) = +2 ke BF(left-child) = −1, lakukan rotasi LR.

ARTIKEL TERKAIT

Penghapusan di Pohon AVL

Penghapusan mengikuti logika yang sama seperti BST biasa dan melakukan penyeimbangan ulang setelahnya.

Langkah 1: Temukan elemen di pohon.

Langkah 2: Hapus node menggunakan penghapusan BST standar.

Langkah 3: Ada dua kemungkinan kasus.

Kasus 1: Menghapus dari subpohon kanan.

  • 1A. If BF(node) = +2 ke BF(left-child) = +1, lakukan rotasi LL.
  • 1B. If BF(node) = +2 ke BF(left-child) = −1, lakukan rotasi LR.
  • 1C. If BF(node) = +2 ke BF(left-child) = 0, lakukan rotasi LL.

Penghapusan di Pohon AVL

Kasus 2: Menghapus dari subpohon sebelah kiri.

  • 2A. If BF(node) = −2 ke BF(right-child) = −1, lakukan rotasi RR.
  • 2B. If BF(node) = −2 ke BF(right-child) = +1, lakukan rotasi RL.
  • 2C. If BF(node) = −2 ke BF(right-child) = 0, lakukan rotasi RR.

Penghapusan di Pohon AVL

C++ Contoh Pohon AVL

Di bawah ini adalah C++ Program yang mengimplementasikan Pohon AVL:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;
};

class AVL {
public:
    struct node *root;

    AVL() {
        this->root = NULL;
    }

    int calheight(struct node *p) {
        if (p->left && p->right) {
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else
                return p->left->height + 1;
        }
        else if (p->left && p->right == NULL) {
            return p->left->height + 1;
        }
        else if (p->left == NULL && p->right) {
            return p->right->height + 1;
        }
        return 0;
    }

    int bf(struct node *n) {
        if (n->left && n->right)
            return n->left->height - n->right->height;
        else if (n->left && n->right == NULL)
            return n->left->height;
        else if (n->left == NULL && n->right)
            return -n->right->height;
        return 0;
    }

    struct node *llrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        p->left = tp->right;
        tp->right = p;
        return tp;
    }

    struct node *rrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        p->right = tp->left;
        tp->left = p;
        return tp;
    }

    struct node *rlrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        struct node *tp2 = p->right->left;
        p->right = tp2->left;
        tp->left = tp2->right;
        tp2->left = p;
        tp2->right = tp;
        return tp2;
    }

    struct node *lrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        struct node *tp2 = p->left->right;
        p->left = tp2->right;
        tp->right = tp2->left;
        tp2->right = p;
        tp2->left = tp;
        return tp2;
    }

    struct node *insert(struct node *r, int data) {
        if (r == NULL) {
            r = new struct node;
            r->data = data;
            r->left = r->right = NULL;
            r->height = 1;
            return r;
        }
        if (data < r->data)
            r->left = insert(r->left, data);
        else
            r->right = insert(r->right, data);

        r->height = calheight(r);

        if (bf(r) == 2 && bf(r->left) == 1)       r = llrotation(r);
        else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r);
        else if (bf(r) == -2 && bf(r->right) == 1)  r = rlrotation(r);
        else if (bf(r) == 2 && bf(r->left) == -1)   r = lrrotation(r);

        return r;
    }

    void levelorder_newline() {
        if (this->root == NULL) {
            cout << "\nEmpty tree\n";
            return;
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v) {
        queue<struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);
        while (!q.empty()) {
            cur = q.front();
            q.pop();
            if (cur == NULL && q.size() != 0) {
                cout << "\n";
                q.push(NULL);
                continue;
            }
            if (cur != NULL) {
                cout << " " << cur->data;
                if (cur->left != NULL)  q.push(cur->left);
                if (cur->right != NULL) q.push(cur->right);
            }
        }
    }

    struct node *deleteNode(struct node *p, int data) {
        if (p->left == NULL && p->right == NULL) {
            if (p == this->root) this->root = NULL;
            delete p;
            return NULL;
        }
        struct node *q;
        if (p->data < data)      p->right = deleteNode(p->right, data);
        else if (p->data > data) p->left  = deleteNode(p->left, data);
        else {
            if (p->left != NULL) {
                q = inpre(p->left);
                p->data = q->data;
                p->left = deleteNode(p->left, q->data);
            } else {
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right, q->data);
            }
        }

        if (bf(p) == 2 && bf(p->left) == 1)         p = llrotation(p);
        else if (bf(p) == 2 && bf(p->left) == -1)    p = lrrotation(p);
        else if (bf(p) == 2 && bf(p->left) == 0)     p = llrotation(p);
        else if (bf(p) == -2 && bf(p->right) == -1)  p = rrrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 1)   p = rlrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 0)   p = rrrotation(p);

        return p;
    }

    struct node *inpre(struct node *p) {
        while (p->right != NULL) p = p->right;
        return p;
    }

    struct node *insuc(struct node *p) {
        while (p->left != NULL) p = p->left;
        return p;
    }

    ~AVL() {}
};

int main() {
    AVL b;
    int c, x;
    do {
        cout << "\n1.Display levelorder on newline";
        cout << "\n2.Insert";
        cout << "\n3.Delete\n";
        cout << "\n0.Exit\n";
        cout << "\nChoice: ";
        cin >> c;
        switch (c) {
        case 1: b.levelorder_newline(); break;
        case 2:
            cout << "\nEnter no. "; cin >> x;
            b.root = b.insert(b.root, x);
            break;
        case 3:
            cout << "\nWhat to delete? "; cin >> x;
            b.root = b.deleteNode(b.root, x);
            break;
        case 0: break;
        }
    } while (c != 0);
}

Contoh eksekusi kode di atas:

  1. Salin kode di atas dan simpan dalam sebuah file bernama avl.cpp.
  2. Kompilasi kode:
g++ avl.cpp -o run
  1. Jalankan kodenya.
./run

C++ Contoh Pohon AVL

Keuntungan Pohon AVL

  • Tinggi Pohon AVL selalu seimbang dan tidak pernah tumbuh melebihi batang kayu N.
  • Pencarian lebih cepat daripada Binary Search Tree biasa karena pohon tersebut tidak dapat mengalami degenerasi.
  • Penyeimbangan otomatis terjadi — tidak diperlukan langkah pembangunan ulang.
  • Performa deterministik cocok untuk sistem waktu nyata dan indeks dalam memori.

Pertanyaan Umum Demo Slot

Pohon AVL adalah pohon pencarian biner yang menyeimbangkan diri sendiri di mana faktor keseimbangan setiap simpul tetap berada di {-1, 0, +1}. Rotasi mengembalikan invarian ini pada setiap penyisipan atau penghapusan, menjagaping Pencarian, penyisipan, dan penghapusan terjadi pada waktu O(log n).

Faktor keseimbangan suatu node sama dengan tinggi (subpohon kiri) dikurangi tinggi (subpohon kanan). Nilainya harus berada dalam rentang {-1, 0, +1}. Faktor keseimbangan +2 atau -2 menandakan bahwa penyisipan atau penghapusan telah membuat node tersebut tidak seimbang dan diperlukan rotasi.

Keempat rotasi tersebut adalah LL, RR, LR, dan RL. LL menggunakan rotasi kanan tunggal, RR menggunakan rotasi kiri tunggal, dan LR serta RL adalah rotasi ganda yang menggabungkan satu rotasi pada anak dengan rotasi berlawanan pada simpul.

Penyisipan mengikuti aturan BST standar, kemudian pohon bergerak kembali ke atas untuk memperbarui ketinggian. Jika ada leluhur yang melanggar aturan keseimbangan, satu rotasi tunggal atau ganda akan mengembalikan keseimbangan. Paling banyak satu rotasi per penyisipan diperlukan.

Pohon AVL memiliki keseimbangan yang ketat dengan faktor keseimbangan maksimal satu, sehingga menghasilkan pencarian yang lebih cepat. Pohon Merah-Hitam memungkinkan keseimbangan yang lebih longgar, yang membuat penyisipan dan penghapusan lebih murah tetapi pencarian sedikit lebih lambat. Basis data lebih menyukai pohon merah-hitam untuk beban penulisan yang tinggi.

AVL Trees mendukung pengindeksan basis data dalam memori, metadata sistem file, antrian prioritas, pencarian buku telepon, pemeriksa ejaan, dan beban kerja apa pun yang membutuhkan pencarian deterministik O(log n) ditambah penelusuran berurutan untuk kueri rentang.

Ya. Sistem AI menggunakan AVL Trees untuk tabel simbol, penyimpanan fitur terurut, penyeimbangan pohon kd, dan pencarian tetangga terdekat pada data terstruktur. AVL Trees juga mendukung indeks pengambilan berperingkat dalam alur pencarian cerdas.

Ya. GitHub Copilot dan asisten AI serupa menyusun rutinitas penyisipan, penghapusan, dan rotasi di dalamnya. C++, Java, atau Python, dan menghasilkan pengujian unit yang memverifikasi faktor keseimbangan tetap konstan pada setiap operasi.

Ringkaslah postingan ini dengan: