AVL Tree

AVL Tree, dinamai dari 3 pembuatnya yaitu Adelson, Velski, dan Landis. Merupakan binary tree yang dapat menyeimbangkan dirinya sendiri. AVL Tree selalu memastikan height dari sub tree kiri dan kanannya tidak memiliki perbedaan depth lebih dari 1. Dalam melakukan penyeimbangan tree, diperlukan rotasi. Rotasi penyeimbangan terbagi menjadi 4 kasus:

Left Rotation

Jika suatu tree menjadi tidak seimbang, ketika sebuah node di insert ke kanan bagian kanan subtree, kita melakukan single left rotation.

Right Rotation

Jika suatu tree menjadi tidak seimbang, ketika sebuah node di insert ke kiri bagian kiri subtree, kita melakukan single right rotation.

Left Right Rotation

Jika suatu tree menjadi tidak seimbang, ketika sebuah node di insert ke kanan bagian kiri subtree, kita melakukan double left right rotation, yaitu left rotation diikuti dengan right rotation.

Right Left Rotation

Jika suatu tree menjadi tidak seimbang, ketika sebuah node di insert ke kiri bagian kanan subtree, kita melakukan double right left rotation, yaitu right rotation diikuti dengan left rotation.

Contoh Implementasi AVL Tree

Insert: 5, 6, 7, 0, 4, 3, 8

Delete: 3, 4, 8

#include <stdio.h> #include <stdlib.h> struct node{ int key; int height; struct node *left; struct node *right; }; struct node *root = 0; int height(struct node *depth){ if (depth == NULL){ return 0; } return depth->height; } struct node *createNode(int key){ struct node *temp = (struct node*) malloc(sizeof(struct node)); temp->key = key; temp->height = 1; temp->left = temp->right = NULL; return(temp); } int checkHeight(node *curr){ int x = height(curr->left); int y = height(curr->right); if (y > x){ return y + 1; } return x + 1; } int checkBalance(struct node *depth){ if (depth == NULL){ return 0; } return height(depth->left) - height(depth->right); } struct node *rotateLeft(node *l){ node *r = l->right; node *tmp = r->left; r->left = l; l->right = tmp; l->height = checkHeight(l); r->height = checkHeight(r); return r; } struct node *rotateRight(node *r){ node *l = r->left; node *tmp = l->right; l->right = r; r->left = tmp; r->height = checkHeight(r); l->height = checkHeight(l); return l; } struct node *insert(struct node *curr, int key){ if (curr == NULL){ return(createNode(key)); } if (key < curr->key){ curr->left = insert(curr->left, key); } else if (key > curr->key){ curr->right = insert(curr->right, key); } else{ printf("Duplicate key detected...\n"); return curr; } curr->height = checkHeight(curr); int balance = checkBalance(curr); //LL if (balance > 1 && key < curr->left->key){ return rotateRight(curr); } //RR if (balance < -1 && key > curr->right->key){ return rotateLeft(curr); } //LR if (balance > 1 && key > curr->left->key){ curr->left = rotateLeft(curr->left); return rotateRight(curr); } //RL if (balance < -1 && key < curr->right->key){ curr->right = rotateRight(curr->right); return rotateLeft(curr); } return curr; } struct node *deleteNode(node *curr, int key){ if (curr == NULL){ return NULL; } else if (key < curr->key){ curr->left = deleteNode(curr->left, key); } else if (key > curr->key){ curr->right = deleteNode(curr->right, key); } else{ if (curr->left == NULL && curr->right == NULL){ free(curr); curr = NULL; } else if (curr->left == NULL || curr->right == NULL){ struct node *temp; if (curr->left == NULL){ temp = curr->right; } else{ temp = curr->left; } free(curr); curr = temp; } else{ struct node *temp = curr->left; while (temp->right != NULL){ temp = temp->right; } curr->key = temp->key; curr->left = deleteNode(curr->left, curr->key); } } if (curr == NULL){ return curr; } curr->height = checkHeight(curr); int balance = checkBalance(curr); //LL if (balance > 1 && key < curr->left->key){ return rotateRight(curr); } //RR if (balance < -1 && key > curr->right->key){ return rotateLeft(curr); } //LR if (balance > 1 && key > curr->left->key){ curr->left = rotateLeft(curr->left); return rotateRight(curr); } //RL if (balance < -1 && key < curr->right->key){ curr->right = rotateRight(curr->right); return rotateLeft(curr); } return curr; } void preOrder(struct node *curr){ printf("%d ", curr->key); if (curr->left != NULL){ preOrder(curr->left); } if (curr->right != NULL){ preOrder(curr->right); } } void inOrder(struct node *curr){ if (curr->left != NULL){ inOrder(curr->left); } printf("%d ", curr->key); if (curr->right != NULL){ inOrder(curr->right); } } void postOrder(struct node *curr){ if (curr->left != NULL){ postOrder(curr->left); } if (curr->right != NULL){ postOrder(curr->right); } printf("%d ", curr->key); } void printTree(){ printf("Preorder Traversal :\n"); preOrder(root); printf("\nInorder Traversal :\n"); inOrder(root); printf("\nPostorder Traversal :\n"); postOrder(root); } void freeTree(struct node *curr){ if (curr->left != NULL){ freeTree(curr->left); } if (curr->right != NULL){ freeTree(curr->right); } free(curr); } int main(){ printf("Insert: 5\n"); root = insert(root, 5); printTree(); printf("\n\n"); printf("Insert: 6\n"); root = insert(root, 6); printTree(); printf("\n\n"); printf("Insert: 7\n"); root = insert(root, 7); printTree(); printf("\n\n"); printf("Insert: 0\n"); root = insert(root, 0); printTree(); printf("\n\n"); printf("Insert: 4\n"); root = insert(root, 4); printTree(); printf("\n\n"); printf("Insert: 3\n"); root = insert(root, 3); printTree(); printf("\n\n"); printf("Insert: 8\n"); root = insert(root, 8); printTree(); printf("\n\n"); printf("Delete: 3\n"); root = deleteNode(root, 3); printTree(); printf("\n\n"); printf("Delete: 4\n"); root = deleteNode(root, 4); printTree(); printf("\n\n"); printf("Delete: 8\n"); root = deleteNode(root, 8); printTree(); printf("\n"); printf("Created by:\n"); printf("Nama: Ryan Frederick Muliawan\n"); printf("NIM: 2301875080\n"); printf("Exiting simulation..."); printf("\n\n"); if (root != NULL){ freeTree(root); } return 0; }