fbpx

Struktur Data : Implementasi AVL Tree dalam Bahasa C

Menambahkan Simpul Baru

Pertama kita akan memodifikasi structure yang digunakan untuk membuat simpul-simpul pada tree. Pada AVL Tree, kita memerlukan informasi height atau tinggi pohon untuk memeriksa keseimbangan pohon. Pada struct node, kita tambahkan satu elemen tambahan:

int height;

Saat kita ingin membuat sebuah simpul baru, kita menggunakan fungsi struct node *newNode(int data). Pada fungsi tersebut, kita tambahkan satu baris program untuk menginisialisasi nilai height.

new_node->height = 1;

Simpul baru pada awalnya ditambahkan sebagai daun, oleh karena itu heightnya bernilai 1.

Kemudian, kita modifikasi fungsi insert. Perbedaan AVL Tree dibandingkan dengan BST adalah AVL Tree selalu memastikan keseimbangan pohon setiap kali ada simpul baru yang ditambahkan atau dihapus dari pohon (self balancing binary search tree). Tahapan untuk menambahkan simpul baru pada AVL Tree adalah sebagai berikut:

  1. Lakukan insert seperti halnya pada BST
  2. Perbarui height untuk seluruh node, mulai dari node yang terakhir ditambahkan hingga ke root. Height node adalah height subtree kiri atau subtree kanan yang ada di bawahnya ditambahkan dengan 1.
  3. Hitung balance factor untuk seluruh node, mulai dari node yang terakhir ditambahkan hingga ke root, untuk menentukan apakah node balanced atau tidak
  4. Jika node unbalanced, lakukan rotasi. Ada 4 kasus rotasi, bergantung kepada posisi node terbawah.
  5. Hasil akhir fungsi adalah mengembalikan node yang telah balanced.

Jika kita perhatikan, tahapan-tahapan di atas dilakukan secara berulang-ulang untuk node-node yang ada pada tree. Oleh karena itu, tahapan tersebut akan diimplementasikan secara rekursif. Jika diimplementasikan, kelima tahapan di atas dapat dituliskan seperti berikut ini.

struct node* insert(struct node* root, int newData)
{
    //1. Lakukan BST insert biasa
    if(root == NULL)
    {
        return(newNode(newData));
    }
    //asumsi tidak boleh ada nilai yang sama dalam BST
    if (newData < root->data)
        root->left = insert(root->left, newData);
    else if (newData > root->data)
        root->right = insert(root->right, newData);

    //2. Update height dari node baru sampai root
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    //3. Hitung balance faktor untuk menentukan apakah node balance atau unbalanced
    int balance = getBalanceFactor(root);

    //Jika tidak balance return hasil rotation
    //Kasus 1: Left Left
    if (balance > 1 && newData < root->left->data)
        return rightRotate(root);

    //Kasus 2: Right Right
    if (balance < -1 && newData > root->right->data)
        return leftRotate(root);

    //Kasus 3: Right Left
    if (balance < -1 && newData < root->right->data)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    //Kasus 4: Left Right
    if (balance > 1 && newData > root->left->data)
    {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    //Rreturn node jika balance
    return root;
}

Ganti fungsi insert yang sudah ada di Praktikum9A.c dengan fungsi insert di atas. Perhatikan bahwa pada fungsi insert di atas terdapat beberapa fungsi tambahan yang dipanggil untuk membantu proses insert simpul baru ke dalam AVL Tree, antara lain:

  • max, fungsi untuk mencari tinggi maksimum antara node kiri dan node kanan
  • getHeight, fungsi untuk mencari tinggi sebuah node
  • getBalanceFactor, fungsi untuk menghitung balance faktor sebuah node
  • rightRotate, fungsi untuk rotasi kanan
  • leftRotate, fungsi untuk rotasi kiri
int max(int a, int b)
{
    if (a > b) return a;
    else return b;
}

int getHeight(struct node* N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

//Hitung balance factor untuk node N
int getBalanceFactor(struct node*N)
{
    if (N == NULL)
        return 0;
    return getHeight(N->left) - getHeight(N->right);
}

struct node* rightRotate(struct node *T)
{
    struct node *newRoot = T->left;
    struct node *orphan = newRoot->right;

    //Lakkukan Rotasi
    newRoot->right = T;
    T->left = orphan;

    //Update Height
    T->height = max(getHeight(T->left), getHeight(T->right))+1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right))+1;

    //Return root baru
    return newRoot;
};

struct node *leftRotate(struct node* T)
{
    struct node *newRoot = T->right;
    struct node *orphan = newRoot->left;

    //Lakukan rotasi
    newRoot->left = T;
    T->right = orphan;

    //Update height
    T->height = max(getHeight(T->left), getHeight(T->right))+1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right))+1;

    //Return root baru
    return newRoot;
};

Untuk menguji apakah fungsi insert tersebut bisa dijalankan, cobalah untuk menginisiasi tree dan menambahkan beberapa simpul, lalu menampilkannya secara preorder, inorder, atau postorder. Contoh:

struct Node *root = NULL;
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);

Jika berhasil, maka akan muncul tampilan seperti ini di layar:


Menghapus Sebuah Simpul

Tahapan pada penghapusan simpul AVL Tree mirip dengan tahapan penambahan simpul baru yang telah dijelaskan di atas. Penghapusan simpul pada AVL Tree dilakukan dengan cara yang sama seperti penghapusan simpul pada BST. Namun, setelahnya kita harus mengecek kembali tinggi dan balance
factor untuk setiap node agar keseimbangan pohon tetap terjaga. Tahapan penghapusan simpul pada AVL Tree adalah sebagai berikut:

  • Lakukan delete seperti halnya pada BST
  • Perbarui height untuk seluruh node, mulai dari node yang terakhir ditambahkan hingga ke root. Height node adalah height subtree kiri atau subtree kanan yang ada di bawahnya ditambahkan dengan 1.
  • Hitung balance factor untuk seluruh node, mulai dari node yang terakhir ditambahkan hingga ke root, untuk menentukan apakah node balanced atau tidak
  • Jika node unbalanced, lakukan rotasi. Ada 4 kasus rotasi, bergantung kepada posisi node terbawah.
  • Hasil akhir fungsi adalah mengembalikan node yang telah balanced.
struct node *delete_node(struct node *root, int deletedData)
{
    if(root == NULL)
        return;

    struct node *cursor;
    if(deletedData > root->data)
        root->right = delete_node(root->right, deletedData);
    else if(deletedData < root->data)
        root->left = delete_node(root->left, deletedData);
    else
    {
        //1 CHILD
        if(root->left == NULL)
        {
            cursor = root->right;
            free(root);
            root = cursor;
        }
        else if(root->right == NULL)
        {
            cursor = root->left;
            free(root);
            root = cursor;
        }

        //2 CHILD NODE
        else
        {
            cursor = root->right;
            while(cursor->left != NULL)
            {
                cursor = cursor->left;
            }
            root->data = cursor->data;
            root->right = delete_node(root->right, cursor->data);
        }
    }

    //Jika setelah dilakukan delete, tree kosong maka return root
    if (root == NULL)
        return root;

    //2. Update height dari node
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    //3. Hitung balance factor untuk menentukan apakah root balance atau unbalanced
    int balance = getBalanceFactor(root);

    //Jika tidak balance, return hasil rotation
    //Kasus 1: Left Left
    if (balance > 1 && getBalanceFactor(root->left) >= 0)
        return rightRotate(root);

    //Kasus 2: Right Right
    if (balance < -1 && getBalanceFactor(root->right) <= 0)
        return leftRotate(root);

    //Kasus 3: Right Left
    if (balance < -1 && getBalanceFactor(root->right) > 0)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    //Kasus 4: Left Right
    if (balance > 1 && getBalanceFactor(root->left) < 0)
    {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    return root;
};

Untuk memastikan fungsi delete_node tersebut sudah berjalan, cobalah untuk
menghapus salah satu node pada tree, lalu tampilkan kembali isi tree secara preorder, inorder, atau postorder. Contoh:

root=delete_node(root, 10);

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Tree (Bagian 2), daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up