AVL Tree

20 Comments / By /

Introduction to AVL Tree

In the realm of data structures, AVL Tree stand as a cornerstone, offering efficient storage and retrieval capabilities while maintaining balance. In this comprehensive article, we delve into the intricacies of AVL Trees, exploring their definition, applications, characteristics, types, advantages, disadvantages, and the key reasons for their usage in programming.

AVL Tree

What is AVL Trees

An AVL Tree is a self-balancing binary search tree, named after its inventors Adelson-Velsky and Landis. It maintains a balance factor for each node, ensuring that the height difference between the left and right subtrees of any node is at most one. This balancing property helps in optimizing search, insertion, and deletion operations, resulting in efficient data retrieval.

Why We Use AVL Trees in data structure

AVL Trees are widely used in programming due to their ability to maintain balance, ensuring optimal performance for various operations. By keeping the tree height-balanced, AVL Trees provide consistent time complexity for search, insertion, and deletion operations, making them suitable for applications where data integrity and performance are crucial.

Characteristics of AVL Trees

  1. Self-Balancing: AVL Trees automatically adjust their structure to maintain balance after insertion or deletion operations, ensuring that the height difference between subtrees remains minimal.
  2. Ordered Structure: Similar to binary search trees, AVL Trees maintain the ordering property, where elements in the left subtree are smaller, and elements in the right subtree are larger than the node’s value.
  3. Height-Balanced: The height difference between the left and right subtrees of any node is at most one, ensuring that the tree remains balanced.
  4. Recursive Definition: AVL Trees can be defined recursively, with each subtree also being an AVL Tree.

Types of AVL Trees

  1. Balanced AVL Tree: A standard AVL Tree where the height difference between subtrees of any node is at most one, ensuring optimal balance and performance.
  2. Strict AVL Tree: A stricter variant of AVL Tree where the height difference between subtrees must be exactly one, leading to a more balanced structure but potentially higher overhead for maintenance.

Advantages of AVL Trees

  1. Optimal Performance: AVL Trees provide consistent time complexity for search, insertion, and deletion operations, with worst-case time complexity of O(log n), where n is the number of nodes in the tree.
  2. Balanced Structure: By maintaining balance, AVL Trees ensure that the height of the tree remains minimal, leading to efficient data retrieval and storage.
  3. Dynamic Operations: AVL Trees support dynamic operations like insertion and deletion while automatically adjusting the structure to maintain balance, making them suitable for real-time applications.
  4. Predictable Behavior: The balancing property of AVL Trees ensures predictable and consistent performance, making them reliable for critical systems where data integrity is paramount.

Disadvantages of AVL Trees

  1. Complexity: Implementing and managing AVL Trees can be complex compared to simpler data structures like binary search trees, requiring careful consideration of balancing algorithms and additional overhead for maintenance.
  2. Overhead: Maintaining balance in AVL Trees may require additional memory and computational overhead, especially in scenarios with frequent insertions and deletions.

Code Examples in Various Languages

Below are code examples demonstrating the implementation of an AVL Tree in different programming languages:

AVL Trees in C#

using System;

public class Node
{
    public int data;
    public Node left, right;
    public int height;

    public Node(int item)
    {
        data = item;
        left = right = null;
        height = 1;
    }
}

public class AVLTree
{
    public Node root;

    public AVLTree()
    {
        root = null;
    }

    public int Height(Node N)
    {
        if (N == null)
            return 0;
        return N.height;
    }

    public int Max(int a, int b)
    {
        return (a > b) ? a : b;
    }

    public int GetBalance(Node N)
    {
        if (N == null)
            return 0;
        return Height(N.left) - Height(N.right);
    }

    public Node RightRotate(Node y)
    {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Max(Height(y.left), Height(y.right)) + 1;
        x.height = Max(Height(x.left), Height(x.right)) + 1;

        return x;
    }

    public Node LeftRotate(Node x)
    {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Max(Height(x.left), Height(x.right)) + 1;
        y.height = Max(Height(y.left), Height(y.right)) + 1;

        return y;
    }

    public Node Insert(Node node, int data)
    {
        if (node == null)
            return (new Node(data));

        if (data < node.data)
            node.left = Insert(node.left, data);
        else if (data > node.data)
            node.right = Insert(node.right, data);
        else
            return node;

        node.height = 1 + Max(Height(node.left), Height(node.right));

        int balance = GetBalance(node);

        if (balance > 1 && data < node.left.data)
            return RightRotate(node);

        if (balance < -1 && data > node.right.data)
            return LeftRotate(node);

        if (balance > 1 && data > node.left.data)
        {
            node.left = LeftRotate(node.left);
            return RightRotate(node);
        }

        if (balance < -1 && data < node.right.data)
        {
            node.right = RightRotate(node.right);
            return LeftRotate(node);
        }

        return node;
    }

    public void PreOrder(Node node)
    {
        if (node != null)
        {
            Console.Write(node.data + " ");
            PreOrder(node.left);
            PreOrder(node.right);
        }
    }

    public static void Main(string[] args)
    {
        AVLTree tree = new AVLTree();

        // Insert sample elements
        tree.root = tree.Insert(tree.root, 10);
        tree.root = tree.Insert(tree.root, 20);
        tree.root = tree.Insert(tree.root, 30);
        tree.root = tree.Insert(tree.root, 40);
        tree.root = tree.Insert(tree.root, 50);
        tree.root = tree.Insert(tree.root, 25);

        // Print preorder traversal
        Console.WriteLine("Preorder traversal:");
        tree.PreOrder(tree.root);
    }
}

Output

Preorder traversal:
30 20 10 25 40 50

Explanation: The code demonstrates the insertion of elements into an AaVL Tree and prints its preorder traversal, showing how the tree is balanced after each insertion.

AVL Trees in C

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

// Structure for a node in AVL Tree
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
    int height;
};

// Function to get the height of a node
int height(struct Node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// Function to get the maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Function to create a new node with given data
struct Node *newNode(int data) {
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // New node is initially added at leaf
    return (node);
}

// Function to right rotate subtree rooted with y
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;
}

// Function to left rotate subtree rooted with x
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 data) {
    // Perform normal BST insertion
    if (node == NULL)
        return (newNode(data));

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal keys are not allowed in BST
        return node;

    // Update height of this ancestor node
    node->height = 1 + max(height(node->left), height(node->right));

    // 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 && data < node->left->data)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // return the (unchanged) node pointer
    return node;
}

// Function to print preorder traversal of AVL Tree
void preOrder(struct Node *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// Driver program to test above functions
int main() {
    struct Node *root = NULL;

    // Insert sample elements
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    // Print preorder traversal
    printf("Preorder traversal:\n");
    preOrder(root);

    return 0;
}

Output

Preorder traversal:
30 20 10 25 40 50

Explanation: The code demonstrates the insertion of elements into an AVL Tree and prints its preorder traversal, showing how the tree is balanced after each insertion.

AVL Trees in C++

#include <iostream>
using namespace std;

// Structure for a node in AVL Tree
class Node {
public:
    int data;
    Node *left;
    Node *right;
    int height;

    Node(int data) {
        this->data = data;
        left = right = NULL;
        height = 1;
    }
};

// Function to get the height of a node
int height(Node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// Function to get the maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Function to right rotate subtree rooted with y
Node *rightRotate(Node *y) {
    Node *x = y->left;
    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;
}

// Function to left rotate subtree rooted with x
Node *leftRotate(Node *x) {
    Node *y = x->right;
    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(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
Node *insert(Node *node, int data) {
    // Perform normal BST insertion
    if (node == NULL)
        return new Node(data);

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal keys are not allowed in BST
        return node;

    // Update height of this ancestor node
    node->height = 1 + max(height(node->left), height(node->right));

    // 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 && data < node->left->data)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // return the (unchanged) node pointer
    return node;
}

// Function to print preorder traversal of AVL Tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout << root->data << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// Driver program to test above functions
int main() {
    Node *root = NULL;

    // Insert sample elements
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    // Print preorder traversal
    cout << "Preorder traversal:" << endl;
    preOrder(root);

    return 0;
}

Output

Preorder traversal:
30 20 10 25 40 50

Explanation: The code demonstrates the insertion of elements into an AVL Tree and prints its preorder traversal, showing how the tree is balanced after each insertion.

AVL Trees in Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def height(self, node):
        if node is None:
            return 0
        return node.height

    def max(self, a, b):
        return a if (a > b) else b

    def get_balance(self, node):
        if node is None:
            return 0
        return self.height(node.left) - self.height(node.right)

    def right_rotate(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        y.height = self.max(self.height(y.left), self.height(y.right)) + 1
        x.height = self.max(self.height(x.left), self.height(x.right)) + 1

        return x

    def left_rotate(self, x):
        y = x.right
        T2 = y.left

        y.left = x
        x.right = T2

        x.height = self.max(self.height(x.left), self.height(x.right)) + 1
        y.height = self.max(self.height(y.left), self.height(y.right)) + 1

        return y

    def insert(self, root, data):
        if root is None:
            return Node(data)

        if data < root.data:
            root.left = self.insert(root.left, data)
        elif data > root.data:
            root.right = self.insert(root.right, data)
        else:
            return root

        root.height = self.max(self.height(root.left), self.height(root.right)) + 1

        balance = self.get_balance(root)

        if balance > 1 and data < root.left.data:
            return self.right_rotate(root)

        if balance < -1 and data > root.right.data:
            return self.left_rotate(root)

        if balance > 1 and data > root.left.data:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and data < root.right.data:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def pre_order(self, root):
        if root is not None:
            print(root.data, end=" ")
            self.pre_order(root.left)
            self.pre_order(root.right)

# Driver code
if __name__ == "__main__":
    tree = AVLTree()
    root = None

    # Insert sample elements
    root = tree.insert(root, 10)
    root = tree.insert(root, 20)
    root = tree.insert(root, 30)
    root = tree.insert(root, 40)
    root = tree.insert(root, 50)
    root = tree.insert(root, 25)

    # Print preorder traversal
    print("Preorder traversal:")
    tree.pre_order(root)

Output

Preorder traversal:
30 20 10 25 40 50

Explanation: The code demonstrates the insertion of elements into an AVL Tree and prints its preorder traversal, showing how the tree is balanced after each insertion.

AVL Trees in PHP

<?php
class Node
{
    public $data;
    public $left;
    public $right;
    public $height;

    public function __construct($data)
    {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
        $this->height = 1;
    }
}

class AVLTree
{
    public function height($node)
    {
        if ($node === null) {
            return 0;
        }
        return $node->height;
    }

    public function max($a, $b)
    {
        return ($a > $b) ? $a : $b;
    }

    public function getBalance($node)
    {
        if ($node === null) {
            return 0;
        }
        return $this->height($node->left) - $this->height($node->right);
    }

    public function rightRotate($y)
    {
        $x = $y->left;
        $T2 = $x->right;

        $x->right = $y;
        $y->left = $T2;

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

        return $x;
    }

    public function leftRotate($x)
    {
        $y = $x->right;
        $T2 = $y->left;

        $y->left = $x;
        $x->right = $T2;

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

        return $y;
    }

    public function insert($root, $data)
    {
        if ($root === null) {
            return new Node($data);
        }

        if ($data < $root->data) {
            $root->left = $this->insert($root->left, $data);
        } elseif ($data > $root->data) {
            $root->right = $this->insert($root->right, $data);
        } else {
            return $root;
        }

        $root->height = $this->max($this->height($root->left), $this->height($root->right)) + 1;

        $balance = $this->getBalance($root);

        if ($balance > 1 && $data < $root->left->data) {
            return $this->rightRotate($root);
        }

        if ($balance < -1 && $data > $root->right->data) {
            return $this->leftRotate($root);
        }

        if ($balance > 1 && $data > $root->left->data) {
            $root->left = $this->leftRotate($root->left);
            return $this->rightRotate($root);
        }

        if ($balance < -1 && $data < $root->right->data) {
            $root->right = $this->rightRotate($root->right);
            return $this->leftRotate($root);
        }

        return $root;
    }

    public function preOrder($root)
    {
        if ($root !== null) {
            echo $root->data . " ";
            $this->preOrder($root->left);
            $this->preOrder($root->right);
        }
    }
}

// Driver code
$tree = new AVLTree();
$root = null;

// Insert sample elements
$root = $tree->insert($root, 10);
$root = $tree->insert($root, 20);
$root = $tree->insert($root, 30);
$root = $tree->insert($root, 40);
$root = $tree->insert($root, 50);
$root = $tree->insert($root, 25);

// Print preorder traversal
echo "Preorder traversal:\n";
$tree->preOrder($root);
?>

Output

Preorder traversal:
30 20 10 25 40 50

Explanation: The code demonstrates the insertion of elements into an AVL Tree and prints its preorder traversal, showing how the tree is balanced after each insertion.

AVL Trees in JAVA

class Node {
    int data, height;
    Node left, right;

    Node(int data) {
        this.data = data;
        height = 1;
        left = right = null;
    }
}

class AVLTree {
    Node root;

    int height(Node node) {
        if (node == null)
            return 0;
        return node.height;
    }

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

    Node rightRotate(Node y) {
        Node x = y.left;
        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;
    }

    Node leftRotate(Node x) {
        Node y = x.right;
        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;
    }

    int getBalance(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int data) {
        // Perform normal BST insertion
        if (node == null)
            return (new Node(data));

        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);
        else // Equal keys are not allowed in BST
            return node;

        // Update height of this ancestor node
        node.height = 1 + max(height(node.left), height(node.right));

        // 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 && data < node.left.data)
            return rightRotate(node);

        // Right Right Case
        if (balance < -1 && data > node.right.data)
            return leftRotate(node);

        // Left Right Case
        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // Return the (unchanged) node pointer
        return node;
    }

    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        // Insert sample elements
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        // Print preorder traversal
        System.out.println("Preorder traversal:");
        tree.preOrder(tree.root);
    }
}

Output

Preorder traversal:
30 20 10 25 40 50

Explanation: The code demonstrates the insertion of elements into an AVL Tree and prints its preorder traversal, showing how the tree is balanced after each insertion.

Conclusion

In conclusion, AVL Trees serve as indispensable tools in the domain of data structures, offering efficient storage, retrieval, and balancing capabilities. By understanding their characteristics, advantages, and disadvantages, developers can leverage the power of AVL Trees to design and implement optimized solutions for various programming challenges. With their balanced performance and dynamic operations, AVL Trees continue to play a vital role in software development, ensuring reliable and efficient data management.

For more visit my website Codelikechamp.com

If you face any issue regarding this topic or any other topic please ask or contact me without any hesitation.

🤞 Don’t miss any latest posts!

Please subscribe by joining our community for free and stay updated!!!

IF YOU HAVE ALREADY SUBSCRIBED JUST CLOSE THIS FORM !

Related Posts

20 thoughts on “AVL Tree”

  1. NeuroTest reviews

    Its like you read my mind You appear to know so much about this like you wrote the book in it or something I think that you can do with a few pics to drive the message home a little bit but instead of that this is excellent blog A fantastic read Ill certainly be back

    Reply
  2. aeroslim reviews

    Somebody essentially lend a hand to make significantly articles Id state That is the very first time I frequented your website page and up to now I surprised with the research you made to make this actual submit amazing Wonderful task

    Reply
  3. Joint Plus CBD reviews

    Thank you for reaching out! If you have any specific questions or topics in mind, please feel free to share them, and I’ll do my best to assist you. Whether you’re curious about a particular technology, scientific concept, literary work, or anything else, I’m here to provide information, advice, or engage in a discussion. Don’t hesitate to let me know how I can help you further!

    Reply
  6. ikaria juice

    Your writing is so refreshing and authentic It’s like having a conversation with a good friend Thank you for opening up and sharing your heart with us

    Reply
  8. cerebrozen

    I sincerely enjoyed what you have produced here. The design is refined, your authored material trendy, yet you appear to have obtained a degree of apprehension regarding what you aim to offer next. Certainly, I shall return more frequently, just as I have been doing almost constantly, provided you uphold this incline.

    Reply
  9. zencortex reviews

    What a fantastic resource! The articles are meticulously crafted, offering a perfect balance of depth and accessibility. I always walk away having gained new understanding. My sincere appreciation to the team behind this outstanding website.

    Reply
  10. aeroslim

    Thank you for your response! I’m grateful for your willingness to engage in discussions. If there’s anything specific you’d like to explore or if you have any questions, please feel free to share them. Whether it’s about emerging trends in technology, recent breakthroughs in science, intriguing literary analyses, or any other topic, I’m here to assist you. Just let me know how I can be of help, and I’ll do my best to provide valuable insights and information!

    Reply

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top