Revised Version

AVL Tree (Adelson-Velsky and Landis Tree)

AVL tree merupakan sebuah self balanced BST dimana setiap nodenya mempertahankan perbedaan tinggi antara node kiri dan node kananya yang disebut balance factor. Nilai balance factor pada AVL tidak boleh melebihi 1.

Terminologi AVL Tree

AVL memiliki terminology yang sama seperti pada modul sebelumnya, hanya terdapat beberapa tambahan terminology yang belum dibahas sebelumnya.

Height : banyaknya tingkatan/level dalam suatu tree.
Balance Factor : selisih antara height node kiri dengan node kanan
Ancestor : seluruh node yang terletak diatas node dan memiliki jalur yang sama

Balance Factor merupakan hasil dari pengurangan height node child kiri dikurang height node child kanan. Dapat juga ditulis sebagai berikut :

$$ Balance Factor = Height Subtree Kiri - Height Subtree Kanan $$

Sumber Gambar : https://static.javatpoint.com/ds/images/avl-tree.png

Dengan begitu, nilai valid Balance Factor hanya berikut ini $$Balance Factor = Height Subtree Kiri - Height Subtree Kanan= {-1, 0, 1} $$ Jika nilai nya diluar angka angka tersebut, maka tree tersebut imbalanced

Representasi Node

Link Implementasi Lengkap AVL Tree dapat dilihat di sini >

Representasi node pada AVL Tree sama dengan BST hanya saja ada tambahan data berupa tinggi pada tiap nodenya.

typedef struct AVLNode_t
{
    int data;
    struct AVLNode_t *left,*right;
    int height;
}AVLNode;

typedef struct AVL_t
{
    AVLNode *_root;
    unsigned int _size;
}AVL;

Untuk menginisiasi sebuah AVl kita bisa menggunakan fungsi avl_init().

void avl_init(AVL *avl) {
    avl->_root = NULL;
    avl->_size = 0u;
}

Variable height digunakan untuk mendapatkan balance factor dari suatu node.

int _getHeight(AVLNode* node){
    if(node==NULL)
        return 0; 
    return node->height;
}

Rotasi

AVL sendiri akan menyeimbangkan dirinya dengan merotasi tree tersebut hingga tree tersebut menjadi balanced.

Terdapat 2 macam rotasi utama yang dipakai dalam avl yaitu Rotasi Right dan Rotasi Left. Untuk menentukan rotasi apa yang harus dilakukan maka pertama kita harus tahu balance factor dari tree tersebut dengan membandingkan selisih antara height subtree kiri dan height subtree kanan.

int _getBalanceFactor(AVLNode* node){
    if(node==NULL)
        return 0;
    return _getHeight(node->left)-_getHeight(node->right);
}

Dari balance factor tersebut kita memiliki 4 kemunkinan kejadian:

Apabila Balance Factor > 1 / tinggi subtree kiri > tinggi subtree kanan :
- Apabila tinggi subtree kiri > subtree kanan (Case left skewed) -> Rotasi Right/LL Cased
- Apabila tinggi subtree kiri < subtree kanan (Case left right zigzag) -> Rotasi Left Diikuti Rotasi Right
Apabila Balance Factor < -1 / tinggi subtree kanan > tinggi subtree kiri :
- Apabila tinggi subtree kanan > subtree kiri (Case right skewed) -> Rotasi Left/RR Cased
- Apabila tinggi subtree kanan < subtree kiri (Case right left zigzag) -> Rotasi Right Diikuti Rotasi Left

Terdapat dua macam rotasi yang digunakan, yaitu rotasi kiri dan kanan.

Rotasi Kanan (Case Left-Skewed)

AVLNode* _rightRotate(AVLNode* pivotNode){

    AVLNode* newParrent=pivotNode->left;
    pivotNode->left=newParrent->right;
    newParrent->right=pivotNode;

    pivotNode->height=_max(_getHeight(pivotNode->left),
                    _getHeight(pivotNode->right))+1;
    newParrent->height=_max(_getHeight(newParrent->left),
                    _getHeight(newParrent->right))+1;
    
    return newParrent;
}

pivotNode merupakan current Node kita yang akan kita jadikan patokan rotasi.

Untuk rotasi kanan caranya adalah child sebelah kiri dari pivotNode menjadi parent baru. Kemudian anak sebelah kanan dari parent baru akan menjadi left child dari pivotNode. Kemudian pivotNode akan menjadi right child dari parent baru. Kemudian lakukan update height untuk pivotNode dan newParrent node.

check

Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/RR%20Rotation.png

**Right rotation** ini bisa menyelesaikan permasalahan untuk **Case Left Skewed**.

```c
AVLNode* _leftCaseRotate(AVLNode* node){
    return _rightRotate(node);
}
```

![](img/m3-2.png)

Rotasi Kiri (Case Right-Skewed)

AVLNode* _leftRotate(AVLNode* pivotNode){

    AVLNode* newParrent=pivotNode->right;
    pivotNode->right=newParrent->left;
    newParrent->left=pivotNode;

    pivotNode->height=_max(_getHeight(pivotNode->left),
                    _getHeight(pivotNode->right))+1;
    newParrent->height=_max(_getHeight(newParrent->left),
                    _getHeight(newParrent->right))+1;
    
    return newParrent;
}

Pada rotasi kiri caranya adalah right child dari pivotNode akan menjadi menjadi parent baru. Kemudian left child dari newParent akan menjadi right child pivotNode. Kemudian pivotNode akan menjadi right child dari parent baru. Kemudian lakukan update height untuk pivotNode dan newParrent node.

check

Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/LL%20Rotation.png

**Left Rotation** ini bisa menyelesaikan permasalahan untuk **Case Right Skewed**.

```c
AVLNode* _rightCaseRotate(AVLNode* node){
    return _leftRotate(node);
}
```

Case Left-Right Zig-zag

Case left right zigzag bisa diselesaikan menggunakan left rotation diikuti right rotation.

AVLNode* _leftRightCaseRotate(AVLNode* node){
    node->left=_leftRotate(node->left);
    return _rightRotate(node);
}

Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/LR%20Rotation.png

Case Right-Left Zig-zag

AVLNode* _rightLeftCaseRotate(AVLNode* node){
    node->right=_rightRotate(node->right);
    return _leftRotate(node);
}

Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/RL%20Rotation.png

Search dan Insertion

Dalam melakukan insert pada sebuah AVL kita perlu terlebih dahulu melakukan insert newnode standar seperti BST. Kemudian update nilai height setiap ancestor newnode. Untuk nilai height pada leaf adalah 1( nilai ini dipilih agar lebih mudah dalam menghandle empty node). Untuk setiap node selain leaf heightnya adalah nilai tertinggi diantara kedua childnya ditambah 1. Kemudian lakukan pengecekan terhadap balance factor setiap ancestor nodenya. Balance factor bisa didapat dari tinggi node kiri dikurangi tinggi node kanan. Jika ditemukan ada node yang tidak balance maka akan dilakukan rotasi.

Fungsi Utilitas

Untuk membuat sebuah node baru.

// Fungsi untuk membuat sebuah node baru
AVLNode* _avl_createNode(int value) {
    // Alokasi memori untuk node baru
    AVLNode *newNode = (AVLNode*) malloc(sizeof(AVLNode));
    // Mengisi data node dengan nilai yang diberikan
    newNode->data = value;
    // Mengatur tinggi node menjadi 1
    newNode->height = 1;
    // Mengatur pointer ke anak kiri dan kanan menjadi NULL
    newNode->left = newNode->right = NULL;
    // Mengembalikan pointer ke node baru
    return newNode;
}

Untuk melakukan pencarian node dengan nilai tertentu.

// Fungsi untuk mencari sebuah node dengan nilai tertentu
AVLNode* _search(AVLNode *root, int value) {
    // Iterasi selama root tidak NULL
    while (root != NULL) {
        // Jika nilai lebih kecil, pergi ke anak kiri
        if (value < root->data)
            root = root->left;
        // Jika nilai lebih besar, pergi ke anak kanan
        else if (value > root->data)
            root = root->right;
        // Jika nilai sama, kembalikan node saat ini
        else
            return root;
    }
    // Jika node tidak ditemukan, kembalikan NULL
    return root;
}

Fungsi utilitas untuk melakukan insert data dalam sebuah AVL.

// Fungsi utilitas untuk melakukan insert data ke dalam sebuah AVL
AVLNode* _insert_AVL(AVL *avl, AVLNode* node, int value) {
    // Jika node NULL, buat node baru
    if (node == NULL)
        return _avl_createNode(value);
    // Jika nilai lebih kecil, masukkan ke subtree kiri
    if (value < node->data)
        node->left = _insert_AVL(avl, node->left, value);
    // Jika nilai lebih besar, masukkan ke subtree kanan
    else if (value > node->data)
        node->right = _insert_AVL(avl, node->right, value);
    
    // Update tinggi dari node saat ini
    node->height = 1 + _max(_getHeight(node->left), _getHeight(node->right));

    // Menghitung faktor keseimbangan untuk node saat ini
    int balanceFactor = _getBalanceFactor(node);
    
    // Memeriksa dan menyesuaikan keseimbangan jika diperlukan
    if (balanceFactor > 1 && value < node->left->data)
        return _leftCaseRotate(node);
    if (balanceFactor > 1 && value > node->left->data)
        return _leftRightCaseRotate(node);
    if (balanceFactor < -1 && value > node->right->data)
        return _rightCaseRotate(node);
    if (balanceFactor < -1 && value < node->right->data)
        return _rightLeftCaseRotate(node);
    
    // Mengembalikan node yang mungkin telah dirotasi
    return node;
}

Fungsi Utama

Fungsi utama untuk mencari sebuah nilai.

// Fungsi untuk mengecek apakah sebuah nilai ada dalam AVL atau tidak
bool avl_find(AVL *avl, int value) {
    // Mencari node dengan nilai yang diberikan
    AVLNode *temp = _search(avl->_root, value);
    // Jika node tidak ditemukan, kembalikan false
    if (temp == NULL)
        return false;
    
    // Jika nilai ditemukan, kembalikan true
    if (temp->data == value)
        return true;
    // Jika nilai tidak ditemukan, kembalikan false
    else
        return false;
}

Fungsi utama untuk memasukan sebuah data.

// Fungsi untuk memasukkan sebuah nilai ke dalam AVL
void avl_insert(AVL *avl, int value) {
    // Hanya memasukkan nilai jika belum ada dalam AVL
    if (!avl_find(avl, value)) {
        // Memanggil fungsi insert dan meng-update root
        avl->_root = _insert_AVL(avl, avl->_root, value);
        // Menambahkan ukuran AVL
        avl->_size++;
    }
}

Deletion

Tidak jauh berbeda dengan melakukan insert pada AVL dalam melakukan remove pada sebuah AVL kita perlu terlebih dahulu melakukan remove standar seperti BST. Kemudian update nilai height setiap ancestor node. Kemudian lakukan pengecekan terhadap balance factor setiap ancestor nodenya. Jika ditemukan ada node yang tidak balance maka akan dilakukan rotasi.

Fungsi Utilitas

// Fungsi untuk mencari node dengan nilai terkecil dalam sebuah subtree
AVLNode* _findMinNode(AVLNode *node) {
    // Mengatur node awal untuk iterasi
    AVLNode *currNode = node;
    // Iterasi hingga menemukan node dengan nilai terkecil
    while (currNode && currNode->left != NULL)
        currNode = currNode->left;
    // Mengembalikan node dengan nilai terkecil
    return currNode;
}

// Fungsi untuk menghapus sebuah node dari AVL
AVLNode* _remove_AVL(AVLNode* node, int value) {
    // Jika node NULL, kembalikan NULL
    if (node == NULL)
        return node;

    // Mencari node yang akan dihapus
    if (value > node->data)
        node->right = _remove_AVL(node->right, value);
    else if (value < node->data)
        node->left = _remove_AVL(node->left, value);
    else {
        // Node ditemukan
        AVLNode *temp;
        
        // Kasus dengan satu anak atau tanpa anak
        if ((node->left == NULL) || (node->right == NULL)) {
            temp = NULL;
            if (node->left == NULL) temp = node->right;
            else if (node->right == NULL) temp = node->left;
            
            if (temp == NULL) {
                temp = node;
                node = NULL;
            } else
                *node = *temp;
            
            free(temp);
        } else {
            // Kasus dengan dua anak
            // Cari node dengan nilai terkecil pada subtree kanan
            temp = _findMinNode(node->right);
            // Salin data
            node->data = temp->data;
            // Hapus node yang sudah disalin datanya
            node->right = _remove_AVL(node->right, temp->data);
        }
    }

    // Jika node NULL, kembalikan NULL
    if (node == NULL) return node;

    // Update tinggi node
    node->height = _max(_getHeight(node->left), _getHeight(node->right)) + 1;

    // Menghitung faktor keseimbangan
    int balanceFactor = _getBalanceFactor(node);

    // Lakukan rotasi untuk mempertahankan keseimbangan
    if (balanceFactor > 1 && _getBalanceFactor(node->left) >= 0) 
        return _leftCaseRotate(node);

    if (balanceFactor > 1 && _getBalanceFactor(node->left) < 0)
        return _leftRightCaseRotate(node);

    if (balanceFactor < -1 && _getBalanceFactor(node->right) <= 0)
        return _rightCaseRotate(node);

    if (balanceFactor < -1 && _getBalanceFactor(node->right) > 0)
        return _rightLeftCaseRotate(node);

    // Mengembalikan node yang mungkin telah dirotasi
    return node;
}

Fungsi Utama

// Fungsi untuk menghapus sebuah nilai dari AVL
void avl_remove(AVL *avl, int value) {
    // Hanya menghapus jika nilai ditemukan dalam AVL
    if (avl_find(avl, value)) {
        // Memanggil fungsi penghapusan dan meng-update root
        avl->_root = _remove_AVL(avl->_root, value);
        // Mengurangi ukuran AVL
        avl->_size--;
    }
}

AVL Tree (Revised) - lab-kcks/Modul-STRUKDAT GitHub Wiki

Revised Version

AVL Tree (Adelson-Velsky and Landis Tree)

Terminologi AVL Tree

Representasi Node

Rotasi

Rotasi Kanan (Case Left-Skewed)

Rotasi Kiri (Case Right-Skewed)

Case Left-Right Zig-zag

Case Right-Left Zig-zag

Search dan Insertion

Fungsi Utilitas

Fungsi Utama

Deletion

Fungsi Utilitas

Fungsi Utama

⚠️ GitHub.com Fallback ⚠️

AVL Tree (Revised) - lab-kcks/Modul-STRUKDAT GitHub Wiki

Revised Version

AVL Tree (Adelson-Velsky and Landis Tree)

Terminologi AVL Tree

Representasi Node

Rotasi

Rotasi Kanan (Case Left-Skewed)

Rotasi Kiri (Case Right-Skewed)

Case Left-Right Zig-zag

Case Right-Left Zig-zag

Search dan Insertion

Fungsi Utilitas

Fungsi Utama

Deletion

Fungsi Utilitas

Fungsi Utama

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️