Struktur Data : Contoh Program AVL Tree dalam Bahasa C

📋 Daftar Isi

Misalkan AVL Tree yang diinginkan untuk dibuat adalah sebagai berikut

Nomor yang ada di atas nama akan menjadi acuan dalam pembetukan AVL Tree. Output yang diharapkan adalah menampilkan setiap nama urut dari setiap level mulai dari kiri ke kanan. Sehingga dari gambar AVL Tree di atas akan diperoleh output:

Ani Budi Caca Delta Ema Fifi Gogo

Selanjutnya membuat fungsi baru untuk menampilkan output tersebut:

void printLevelOrder(struct node* root)
{
    int h = getHeight(root);
    for(int i = 1; i <= h; i++)
        printCurrentLevel(root, i);
}

void printCurrentLevel(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%s ", root->nama);
    else if (level > 1)
    {
        printCurrentLevel(root->left, level - 1);
        printCurrentLevel(root->right, level - 1);
    }
}

Source Code Lengkap

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node
{
    int nomor;
    char nama[30];
    int height;
    struct node *left;
    struct node *right;

};

typedef struct node* mynode;

mynode createNode(char nama[30], int nomor);
int max(int a, int b);
int getHeight(struct node* N);
int getBalanceFactor(struct node *N);
struct node* rightRotate(struct node *T);
struct node* leftRotate(struct node *T);
mynode insert(struct node* root, char newNama[30], int nonomor);
void displayPreorder(struct node* node);
void displayInorder(struct node* node);
void displayPostorder(struct node* node);
mynode deleteNode(struct node *root, int delNomor);

void printLevelOrder(struct node* root)
{
    int h = getHeight(root);
    for(int i = 1; i <= h; i++)
        printCurrentLevel(root, i);
}

void printCurrentLevel(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%s ", root->nama);
    else if (level > 1)
    {
        printCurrentLevel(root->left, level - 1);
        printCurrentLevel(root->right, level - 1);
    }
}

int main()
{
    mynode root = createNode("Ani", 9);
    //root = insert(root, "Ani", 10);
    root = insert(root, "Budi", 4);
    root = insert(root, "Caca", 12);
    root = insert(root, "Delta", 3);
    root = insert(root, "Ema", 5);
    root = insert(root, "Fifi", 10);
    root = insert(root, "Gogo", 13);


    /*printf("\nIsi dari binary tree (Pre-Order) adalah \n");
    displayPreorder(root);

    printf("\nIsi dari binary tree (In-Order) adalah \n");
    displayInorder(root);

    printf("\nIsi dari binary tree (Post-Order) adalah \n");
    displayPostorder(root);*/

    printf("\nTampil AVL Tree secara urut sesuai level dan dari kiri ke kanan : \n");
    printLevelOrder(root);

    return 0;
}

mynode createNode(char nama[30], int nomor)
{
    mynode newNode = (mynode)malloc(sizeof(struct node));
    strcpy(newNode->nama, nama);
    newNode->nomor = nomor;
    newNode->height = 1;
    newNode->left = newNode->right = NULL;

    return newNode;
};

mynode insert(struct node* root, char newNama[30], int nonomor)
{
    //1. Lakukan BST insert biasa
    if(root == NULL)
    {
        return(createNode(newNama, nonomor));
    }
    //asumsi tidak boleh ada nilai yang sama dalam BST
    if (nonomor < root->nomor)
        root->left = insert(root->left, newNama, nonomor);
    else if (nonomor > root->nomor)
        root->right = insert(root->right, newNama, nonomor);

    //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 && nonomor < root->left->nomor)
        return rightRotate(root);

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

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

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

    //Rreturn node jika balance
    return root;
}

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;
};

void displayPreorder(struct node* node)
{
    if (node == NULL)
        return;

    printf("%s ", node->nama); //root
    displayPreorder(node->left); //subtree kiri
    displayPreorder(node->right); //subtree kanan
}

void displayInorder(struct node* node)
{
    if (node == NULL)
        return;

    displayInorder(node->left); //subtree kiri
    printf("%s ", node->nama); //akar
    displayInorder(node->right); //subtree kanan
}

void displayPostorder(struct node* node)
{
    if (node == NULL)
        return;

    displayPostorder(node->left); //subtree kiri
    displayPostorder(node->right); //subtree kanan
    printf("%s ", node->nama); //root
}

mynode deleteNode(struct node *root, int delNomor)
{
    if(root == NULL)
        return;

    mynode cursor;
    if(delNomor > root->nomor)
        root->right = deleteNode(root->right, delNomor);
    else if(delNomor < root->nomor)
        root->left = deleteNode(root->left, delNomor);
    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->nomor = cursor->nomor;
            root->right = deleteNode(root->right, cursor->nomor);
        }
    }

    //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;
};