Data Structure

007
- 3 May 2020-

Data Structure (Kelas Besar)
Nama : Muhammad Andika Putra
NIM : 2301865994
Kelas : CD-01

AVL Tree

What is an AVL Tree?

An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees.

A BST is a data structure composed of nodes. It has the following guarantees:

Each tree has a root node (at the top).

The root node has zero, one or two child nodes.

Each child node has zero, one or two child nodes, and so on.

Each node has up to two children.

For each node, its left descendants are less than the current node, which is less than the right descendants.

AVL trees have an additional guarantee:

The difference between the depth of right and left subtrees cannot be more than one. In order to maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee.

AVL trees have a worst case lookup, insert and delete time of O(log n).

AVL Insertion Process

You will do an insertion similar to a normal Binary Search Tree insertion. After inserting, you fix the AVL property using left or right rotations.

If there is an imbalance in left child of right subtree, then you perform a left-right rotation.

If there is an imbalance in left child of left subtree, then you perform a right rotation.

If there is an imbalance in right child of right subtree, then you perform a left rotation.

If there is an imbalance in right child of left subtree, then you perform a right-left rotation.

An AVL tree is a self-balancing binary search tree. An AVL tree is a binary search tree which has the following properties: ->The sub-trees of every node differ in height by at most one. ->Every sub-tree is an AVL tree.

AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree.

AVL Tree Rotations

In AVL tree, after performing every operation like insertion and deletion we need to check the balance factor of every node in the tree. If every node satisfies the balance factor condition then we conclude the operation otherwise we must make it balanced. We use rotation operations to make the tree balanced whenever the tree is becoming imbalanced due to any operation.

Rotation operations are used to make a tree balanced.There are four rotations and they are classified into two types:

Single Left Rotation (LL Rotation)

In LL Rotation every node moves one position to left from the current position.

Single Right Rotation (RR Rotation)

In RR Rotation every node moves one position to right from the current position.

Left Right Rotation (LR Rotation)

The LR Rotation is combination of single left rotation followed by single right rotation. In LR Rotation, first every node moves one position to left then one position to right from the current position.

Right Left Rotation (RL Rotation)

The RL Rotation is combination of single right rotation followed by single left rotation. In RL Rotation, first every node moves one position to right then one position to left from the current position.

Time Analysis Of AVL Trees

AVL tree is binary search tree with additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1.

Algorithm Average Worst case: Space: O(n), Time: O(n)

Application of AVL Trees

AVL trees are beneficial in the cases where you are designing some database where insertions and deletions are not that frequent but you have to frequently look-up for the items present in there.

Code for AVL Tree:

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

/ \

20 40

/ \ \

10 25 50

printf("Preorder traversal of the constructed AVL"

" tree is \n");

preOrder(root);

return 0;

}

Sumber:
https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

Search This Blog

Data Structure

Comments

Post a Comment