AVL TREE

Hai semuanya, sudah lama saya tidak mengupdate blog saya dan kali ini saya akan update mengenai lanjutan dari data structure yaitu AVL Tree, materi AVL Tree ini secara tidak langsung berhubungan dengan Tree yang pernah saya bahas sebelumnya. Jadi sangat di rekomendasi untuk membaca atau mengerti materi Tree dan Binary Search Tree sebelum membaca Blog ini agar anda lebih mudah memahami konsep Adelson-Velskii dan Landis Tree alias AVL Tree.

AVL Tree adalah cabang tipe dari binary search tree, node node yang dimasukan pun juga sama seperti binary search tree dengan tambahan AVL tree harus seimbang. Maksud dari seimbang adalah perbedaan tinggi tinggi nodenya tidak lebih dari 1, mari kita bahas apa saja komposisi yang dipunyai avl tree. Sebuah AVL tree harus mempunyai root, root tersebut tidak mempunyai anak atau mempunyai satu atau dua anak, anakan dari root tidak mempunyai anak atau mempunyai satu atau dua anak, tiap anak hanya bisa maksimal mempunyai dua anak, tiap node anak kirinya pasti lebih kecil dan kanannnya pasti lebih besar sebagaimana seperti BST. Syarat AVL Tree menambahkan bahwa perbedaan antara kedalaman subtrees kanan dan kiri tidak boleh lebih dari satu. Untuk menjaga jaminan ini, implementasi AVL akan mencakup algoritma untuk menyeimbangkan kembali pohon saat menambahkan elemen tambahan akan mengganggu jaminan ini.

AVL Tree juga memiliki insert dan deletenya sendiri, karena dia harus selalu menjadi tree yang stabil / seimbang maka akan saya bahas beberapa cara yang dapat terjadi untuk menyeimbangkan AVL Tree ini, cara ini akan dibagi menjadi 4 yaitu :
- Jika ada ketidakseimbangan pada anak kiri subtree kanan, maka kita melakukan rotasi kiri-kanan
- Jika ada ketidakseimbangan pada anak kiri subtree kiri, maka kita melakukan rotasi kanan
- Jika ada ketidakseimbangan pada anak kanan subtree kanan, maka kita melakukan rotasi kiri
- Jika ada ketidakseimbangan pada anak kanan subtree kiri, maka kita melakukan rotasi kanan-kiri

Berikut saya akan berika kode yang saya ambil dari codesdope.com untuk dipelajari bersama sama mengenai AVL Tree, terima kasih kepada codesdope.com karena telah menyediakan kodingan ini.

Contoh kode :

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

typedef struct avl_node {
  int data;
  struct avl_node *left;
  struct avl_node *right;
  struct avl_node *parent;
  int height;
}avl_node;

typedef struct avl_tree {
  avl_node *root;
}avl_tree;

avl_node* new_avl_node(int data) {
  avl_node *n = malloc(sizeof(avl_node));
  n->data = data;
  n->left = NULL;
  n->right = NULL;
  n->parent = NULL;
  n->height = 0;

  return n;
}

avl_tree* new_avl_tree() {
  avl_tree *t = malloc(sizeof(avl_tree));
  t->root = NULL;

  return t;
}

int max(int a, int b) {
  if(a > b)
    return a;
  return b;
}

int height(avl_node *n) {
  if(n == NULL)
    return -1;
  return n->height;
}

avl_node* minimum(avl_tree *t, avl_node *x) {
  while(x->left != NULL)
    x = x->left;
  return x;
}

void left_rotate(avl_tree *t, avl_node *x) {
  avl_node *y = x->right;
  x->right = y->left;
  if(y->left != NULL) {
    y->left->parent = x;
  }
  y->parent = x->parent;
  if(x->parent == NULL) { //x is root
    t->root = y;
  }
  else if(x == x->parent->left) { //x is left child
    x->parent->left = y;
  }
  else { //x is right child
    x->parent->right = y;
  }
  y->left = x;
  x->parent = y;

  x->height = 1 + max(height(x->left), height(x->right));
  y->height = 1 + max(height(y->left), height(y->right));
}

void right_rotate(avl_tree *t, avl_node *x) {
  avl_node *y = x->left;
  x->left = y->right;
  if(y->right != NULL) {
    y->right->parent = x;
  }
  y->parent = x->parent;
  if(x->parent == NULL) { //x is root
    t->root = y;
  }
  else if(x == x->parent->right) { //x is left child
    x->parent->right = y;
  }
  else { //x is right child
    x->parent->left = y;
  }
  y->right = x;
  x->parent = y;

  x->height = 1 + max(height(x->left), height(x->right));
  y->height = 1 + max(height(y->left), height(y->right));
}

int balance_factor(avl_node *n) {
  if(n == NULL)
    return 0;
  return(height(n->left) - height(n->right));
}

void insert(avl_tree *t, avl_node *n) {
  avl_node *y = NULL;
  avl_node *temp = t->root;
  while(temp != NULL) {
    y = temp;
    if(n->data < temp->data)
      temp = temp->left;
    else
      temp = temp->right;
  }
  n->parent = y;

  if(y == NULL) //newly added node is root
    t->root = n;
  else if(n->data < y->data)
    y->left = n;
  else
    y->right = n;

  avl_node *z = n;

  while(y != NULL) {
    y->height = 1 + max(height(y->left), height(y->right));


    avl_node *x = y->parent;

    if(balance_factor(x) <= -2 || balance_factor(x) >= 2) {//grandparent is unbalanced
      if(y == x->left) {
        if(z == x->left->left) //case 1
          right_rotate(t, x);

        else if(z == x->left->right) {//case 3
          left_rotate(t, y);
          right_rotate(t, x);
        }
      }
      else if(y == x->right) {
        if(z == x->right->right) //case 2
          left_rotate(t, x);

        else if(z == x->right->left) {//case 4
          right_rotate(t, y);
          left_rotate(t, x);
        }
      }
      break;
    }
    y = y->parent;
    z = z->parent;
  }
}

void transplant(avl_tree *t, avl_node *u, avl_node *v) {
  if(u->parent == NULL) //u is root
    t->root = v;
  else if(u == u->parent->left) //u is left child
    u->parent->left = v;
  else //u is right child
    u->parent->right = v;

  if(v != NULL)
    v->parent = u->parent;
}

void avl_delete_fixup(avl_tree *t, avl_node *n) {
  avl_node *p = n;

  while(p != NULL) {
    p->height = 1 + max(height(p->left), height(p->right));

    if(balance_factor(p) <= -2 || balance_factor(p) >= 2) { //grandparent is unbalanced
      avl_node *x, *y, *z;
      x = p;

      //taller child of x will be y
      if(x->left->height > x->right->height)
        y = x->left;
      else
        y = x->right;

      //taller child of y will be z
      if(y->left->height > y->right->height) {
        z = y->left;
      }
      else if(y->left->height < y->right->height) {
        z = y->right;
      }
      else { //same height, go for single rotation
        if(y == x->left)
          z = y->left;
        else
          z = y->right;
      }

      if(y == x->left) {
        if(z == x->left->left) //case 1
          right_rotate(t, x);

        else if(z == x->left->right) {//case 3
          left_rotate(t, y);
          right_rotate(t, x);
        }
      }
      else if(y == x->right) {
        if(z == x->right->right) //case 2
          left_rotate(t, x);

        else if(z == x->right->left) {//case 4
          right_rotate(t, y);
          left_rotate(t, x);
        }
      }
    }
    p = p->parent;
  }
}

void avl_delete(avl_tree *t, avl_node *z) {
  if(z->left == NULL) {
    transplant(t, z, z->right);
    if(z->right != NULL)
      avl_delete_fixup(t, z->right);
    free(z);
  }
  else if(z->right == NULL) {
    transplant(t, z, z->left);
    if(z->left != NULL)
      avl_delete_fixup(t, z->left);
    free(z);
  }
  else {
    avl_node *y = minimum(t, z->right); //minimum element in right subtree
    if(y->parent != z) {
      transplant(t, y, y->right);
      y->right = z->right;
      y->right->parent = y;
    }
    transplant(t, z, y);
    y->left = z->left;
    y->left->parent = y;
    if(y != NULL)
      avl_delete_fixup(t, y);
    free(z);
  }
}

void inorder(avl_tree *t, avl_node *n) {
  if(n != NULL) {
    inorder(t, n->left);
    printf("%d\n", n->data);
    inorder(t, n->right);
  }
}

int main() {
  avl_tree *t = new_avl_tree();

  avl_node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j, *k, *l, *m;

  a = new_avl_node(10);
  b = new_avl_node(20);
  c = new_avl_node(30);
  d = new_avl_node(100);
  e = new_avl_node(90);
  f = new_avl_node(40);
  g = new_avl_node(50);
  h = new_avl_node(60);
  i = new_avl_node(70);
  j = new_avl_node(80);
  k = new_avl_node(150);
  l = new_avl_node(110);
  m = new_avl_node(120);

  insert(t, a);
  insert(t, b);
  insert(t, c);
  insert(t, d);
  insert(t, e);
  insert(t, f);
  insert(t, g);
  insert(t, h);
  insert(t, i);
  insert(t, j);
  insert(t, k);
  insert(t, l);
  insert(t, m);

  avl_delete(t, a);
  avl_delete(t, m);

  inorder(t, t->root);

  return 0;
}

Terima kasih banyak kepada semua pembaca, sekian blog saya kali ini semoga bermanfaat untuk kita semua. Sampai jumpa di blog selanjutnya :)

Nama : Viriyaputra Lawijaya
NIM : 2301866845