AVL Tree

AVL Tree

AVL Tree adalah Binary Search Tree (BST) yang dapat menyeimbangkan diri sendiri di mana perbedaan antara ketinggian subtree kiri dan kanan tidak boleh lebih dari satu untuk semua node.

Implementasi AVL Tree

Berikut ini adalah implementasi untuk Penyisipan AVL Tree. Implementasi berikut menggunakan insert BST rekursif untuk memasukan node baru. Dalam insert BST rekursif, setelah insersi, kita mendapatkan pointer ke semua leluhur satu per satu secara Bottom-up atau dari bawah ke atas. Jadi kita tidak perlu parent pointer untuk melakukan perjalanannya. Kode rekursif itu sendiri bergerak ke atas dan mengunjungi semua leluhur dari simpul yang baru dimasukkan.

1) Lakukan pemasangan BST normal.

2) Node saat ini harus menjadi salah satu leluhur dari node yang baru dimasukkan. Perbarui ketinggian node saat ini.

3) Dapatkan faktor keseimbangan (tinggi subtree kiri -  tinggi subtree kanan) dari node saat ini.

4) Jika faktor keseimbangan lebih besar dari 1, maka simpul saat ini tidak seimbang dan ktia berada dalam Left Left case atau Left Right case. Untuk memeriksa apakah ada Left case atau tidak, bandingkan kunci yang baru dimasukkan dengan kunci di root subtree kiri.

5) Jika faktor keseimbangan kurang dari -1, maka simpul saat ini tidak seimbang dan kami berada dalam Right Right case atau Right Left case. Untuk memeriksa apakah ada Right case atau tidak, bandingkan kunci yang baru dimasukkan dengan kunci di root subtree kanan.

Contoh program dalam C:

// C program to insert a node in AVL tree

#include<stdio.h>

#include<stdlib.h>

  

// An AVL tree node

struct Node

{

    int key;

    struct Node *left;

    struct Node *right;

    int height;

};

  

// A utility function to get maximum of two integers

int max(int a, int b);

  

// A utility function to get the height of the tree

int height(struct Node *N)

{

    if (N == NULL)

        return 0;

    return N->height;

}

  

// A utility function to get maximum of two integers

int max(int a, int b)

{

    return (a > b)? a : b;

}

  

/* Helper function that allocates a new node with the given key and

    NULL left and right pointers. */

struct Node* newNode(int key)

{

    struct Node* node = (struct Node*)

                        malloc(sizeof(struct Node));

    node->key   = key;

    node->left   = NULL;

    node->right  = NULL;

    node->height = 1;  // new node is initially added at leaf

    return(node);

}

  

// A utility function to right rotate subtree rooted with y

// See the diagram given above.

struct Node *rightRotate(struct Node *y)

{

    struct Node *x = y->left;

    struct Node *T2 = x->right;

  

    // Perform rotation

    x->right = y;

    y->left = T2;

  

    // Update heights

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

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

  

    // Return new root

    return x;

}

  

// A utility function to left rotate subtree rooted with x

// See the diagram given above.

struct Node *leftRotate(struct Node *x)

{

    struct Node *y = x->right;

    struct Node *T2 = y->left;

  

    // Perform rotation

    y->left = x;

    x->right = T2;

  

    //  Update heights

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

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

  

    // Return new root

    return y;

}

  

// Get Balance factor of node N

int getBalance(struct Node *N)

{

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}

  

// Recursive function to insert a key in the subtree rooted

// with node and returns the new root of the subtree.

struct Node* insert(struct Node* node, int key)

{

    /* 1.  Perform the normal BST insertion */

    if (node == NULL)

        return(newNode(key));

  

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

    else // Equal keys are not allowed in BST

        return node;

  

    /* 2. Update height of this ancestor node */

    node->height = 1 + max(height(node->left),

                           height(node->right));

  

    /* 3. Get the balance factor of this ancestor

          node to check whether this node became

          unbalanced */

    int balance = getBalance(node);

  

    // If this node becomes unbalanced, then

    // there are 4 cases

  

    // Left Left Case

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);

  

    // Right Right Case

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);

  

    // Left Right Case

    if (balance > 1 && key > node->left->key)

    {

        node->left =  leftRotate(node->left);

        return rightRotate(node);

    }

  

    // Right Left Case

    if (balance < -1 && key < node->right->key)

    {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

  

    /* return the (unchanged) node pointer */

    return node;

}

  

// A utility function to print preorder traversal

// of the tree.

// The function also prints height of every node

void preOrder(struct Node *root)

{

    if(root != NULL)

    {

        printf("%d ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}

  

/* Drier program to test above function*/

int main()

{

  struct Node *root = NULL;

  

  /* Constructing tree given in the above figure */

  root = insert(root, 10);

  root = insert(root, 20);

  root = insert(root, 30);

  root = insert(root, 40);

  root = insert(root, 50);

  root = insert(root, 25);

  

  /* The constructed AVL Tree would be

            30

           /  \

         20   40

        /  \     \

       10  25    50

  */

  

  printf("Preorder traversal of the constructed AVL"

         " tree is \n");

  preOrder(root);

  

  return 0;

}