AVL Trees in Java

AVL trees, named after inventors Adelson-Velsky and Landis, are self-balancing binary search trees that are commonly used in computer science to store data. They are based on the idea of a binary search tree (BST), which is a data structure that allows for efficient access, insertion, and deletion of elements. In this article, we’ll explore what makes AVL trees unique, and how to work with them in Java, including their time and space complexity.

What is an AVL Tree?

An AVL tree is a type of BST with a self-balancing property that helps the tree remain relatively balanced. This self-balancing property is achieved by keeping track of the height of each node. Whenever a node is inserted into the tree, the height is adjusted if necessary to ensure that the tree remains balanced.

If you’re not familiar with BSTs, they are a data structure that allows for efficient searches, insertions, and deletions. A BST is composed of nodes, which contain keys and left and right pointers. The left pointer points to the node with a key that is less than the current node, and the right pointer points to the node with a key that is greater than the current node.

Time Complexity of AVL Trees

The time complexity of an AVL tree is dependent on the height of the tree. The height of the tree is determined by the number of nodes in the tree. The following is the average case time complexity for searching, inserting, and deleting elements in an AVL tree.

• Search: O(log n)
• Insert: O(log n)
• Delete: O(log n)

The worst case time complexity for an AVL tree is the same as the average case time complexity.

Space Complexity of AVL Trees

The space complexity of an AVL tree is O(n). This is because an AVL tree has to store the keys and the left and right pointers for each node.

Working with AVL Trees in Java

Now that we’ve discussed the basics of AVL trees, let’s look at how to work with them in Java. We’ll start by looking at how to create an AVL tree.

Creating an AVL Tree

The following is the Java code for creating an AVL tree:

public class AVLTree {
 
    // Root node pointer. Will be null for an empty tree. 
    private Node root; 
 
    // Node class. Each node has a left and right pointer, and a data element. 
    private class Node { 
        int data; 
        Node left; 
        Node right; 
 
        public Node(int data) { 
            this.data = data; 
        } 
    } 
 
    // Inserts a new node into the tree
    public void insert(int data) { 
        // Create a new node 
        Node newNode = new Node(data); 
 
        // Check if the tree is empty 
        if (root == null) { 
            root = newNode; 
            return; 
        } 
 
        // Find the correct position in the tree and insert the new node 
        insertNode(root, newNode); 
    } 
 
    // Helper function to insert a node into the tree 
    private void insertNode(Node current, Node newNode) { 
        if (newNode.data < current.data) { 
            // Insert new node to the left 
            if (current.left == null) { 
                current.left = newNode; 
            } else { 
                insertNode(current.left, newNode); 
            } 
        } else { 
            // Insert new node to the right 
            if (current.right == null) { 
                current.right = newNode; 
            } else { 
                insertNode(current.right, newNode); 
            } 
        } 
    } 
}

In this code, we create a class called AVLTree, which contains a root node pointer and a Node class. The root node pointer is initially set to null, which indicates that the tree is empty. The Node class contains a data element and left and right pointers.

We then create a public insert() method, which takes an integer as an argument. This method creates a new Node object and checks if the tree is empty. If so, the root is set to the new node. If not, the insertNode() helper method is called to find the correct position in the tree and insert the new node.

Searching an AVL Tree

The following is the Java code for searching an AVL tree:

public Node search(int data) { 
    return searchNode(root, data); 
} 

private Node searchNode(Node current, int data) { 
    if (current == null) { 
        return null; 
    } 
 
    if (data == current.data) { 
        return current; 
    } 
 
    if (data < current.data) { 
        return searchNode(current.left, data); 
    } else { 
        return searchNode(current.right, data); 
    } 
}

In this code, we create a public search() method that takes an integer as an argument. This method calls the searchNode() helper method, which takes the root node and the data to be searched for as arguments. The searchNode() method recursively searches the tree for the data. If the data is found, the node containing the data is returned.

Deleting a Node from an AVL Tree

The following is the Java code for deleting a node from an AVL tree:

public void delete(int data) { 
    root = deleteNode(root, data); 
} 

private Node deleteNode(Node current, int data) { 
    if (current == null) { 
        return null; 
    } 
 
    if (data == current.data) { 
        // Node to be deleted found 
        if (current.left == null && current.right == null) { 
            return null; 
        } 
 
        if (current.left == null) { 
            return current.right; 
        } 
 
        if (current.right == null) { 
            return current.left; 
        } 
 
        int smallestValue = findSmallestValue(current.right); 
        current.data = smallestValue; 
        current.right = deleteNode(current.right, smallestValue); 
        return current; 
    } 
 
    if (data < current.data) { 
        current.left = deleteNode(current.left, data); 
        return current; 
    } 
 
    current.right = deleteNode(current.right, data); 
    return current; 
}

In this code, we create a public delete() method, which takes an integer as an argument. This method calls the deleteNode() helper method, which takes the root node and the data to be deleted as arguments. The deleteNode() method recursively searches the tree for the data. If the data is found, the node containing the data is removed and the tree is rebalanced if necessary.

Conclusion

In this article, we explored the basics of AVL trees and discussed how to work with them in Java. We discussed their time and space complexity, and looked at the code for creating, searching, and deleting nodes from an AVL tree. We also discussed how the tree is self-balancing and how the height of the tree affects its performance.

Exercises

public class AVLTree { 
 
    // Root node pointer. Will be null for an empty tree. 
    private Node root; 
 
    // Node class. Each node has a left and right pointer, and a data element. 
    private class Node { 
        int data; 
        Node left; 
        Node right; 
 
        public Node(int data) { 
            this.data = data; 
        } 
    } 
 
    // Inserts a new node into the tree
    public void insert(int data) { 
        // Create a new node 
        Node newNode = new Node(data); 
 
        // Check if the tree is empty 
        if (root == null) { 
            root = newNode; 
            return; 
        } 
 
        // Find the correct position in the tree and insert the new node 
        insertNode(root, newNode); 
    } 
 
    // Helper function to insert a node into the tree 
    private void insertNode(Node current, Node newNode) { 
        if (newNode.data < current.data) { 
            // Insert new node to the left 
            if (current.left == null) { 
                current.left = newNode; 
            } else { 
                insertNode(current.left, newNode); 
            } 
        } else { 
            // Insert new node to the right 
            if (current.right == null) { 
                current.right = newNode; 
            } else { 
                insertNode(current.right, newNode); 
            } 
        } 
    } 
}

public Node search(int data) { 
    return searchNode(root, data); 
} 

private Node searchNode(Node current, int data) { 
    if (current == null) { 
        return null; 
    } 
 
    if (data == current.data) { 
        return current; 
    } 
 
    if (data < current.data) { 
        return searchNode(current.left, data); 
    } else { 
        return searchNode(current.right, data); 
    } 
}

public void delete(int data) { 
    root = deleteNode(root, data); 
} 

private Node deleteNode(Node current, int data) { 
    if (current == null) { 
        return null; 
    } 
 
    if (data == current.data) { 
        // Node to be deleted found 
        if (current.left == null && current.right == null) { 
            return null; 
        } 
 
        if (current.left == null) { 
            return current.right; 
        } 
 
        if (current.right == null) { 
            return current.left; 
        } 
 
        int smallestValue = findSmallestValue(current.right); 
        current.data = smallestValue; 
        current.right = deleteNode(current.right, smallestValue); 
        return current; 
    } 
 
    if (data < current.data) { 
        current.left = deleteNode(current.left, data); 
        return current; 
    } 
 
    current.right = deleteNode(current.right, data); 
    return current; 
}

private int findSmallestValue(Node root) { 
    if (root.left == null) { 
        return root.data; 
    } 
 
    return findSmallestValue(root.left); 
}

public int height() { 
    return height(root); 
} 

private int height(Node node) { 
    if (node == null) { 
        return 0; 
    } 
 
    return 1 + Math.max(height(node.left), height(node.right)); 
}