AVL Tree Implementation in Java

An AVL tree is a self-balancing binary search tree where the difference between the heights of the left and right subtrees cannot be more than one for all nodes. AVL trees maintain this balance using rotations after each insertion or deletion operation.

Program Structure

The implementation of an AVL tree involves two main classes:

• Node: Represents a node in the AVL tree.
• AVLTree: Manages the AVL tree operations such as insertion, deletion, and balancing.

Node Class

This class represents a node in the AVL tree. Each node contains:

• An integer value key.
• A reference to the left child node.
• A reference to the right child node.
• An integer height to track the height of the node.

AVLTree Class

This class encapsulates the AVL tree operations and contains the following components:

• insert: Inserts a node into the AVL tree while maintaining balance.
• delete: Removes a node from the AVL tree while maintaining balance.
• rotateRight: Performs a right rotation to restore balance.
• rotateLeft: Performs a left rotation to restore balance.
• getHeight: Returns the height of a node.
• getBalance: Returns the balance factor of a node.
• preOrder: Performs a pre-order traversal of the tree.

Java Code Implementation

Node Class


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

Node(int d) {
key = d;
height = 1;
}
}

AVLTree Class


class AVLTree {
Node root;

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

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

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

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

y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

return x;
}

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

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

x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

return y;
}

Node insert(Node node, int key) {
if (node == null)
return (new Node(key));

if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate keys not allowed
return node;

node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

int balance = getBalance(node);

if (balance > 1 && key < node.left.key)
return rotateRight(node);

if (balance < -1 && key > node.right.key)
return rotateLeft(node);

if (balance > 1 && key > node.left.key) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}

if (balance < -1 && key < node.right.key) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}

return node;
}

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

Explanation

Here is a detailed explanation of the key components in the AVL tree implementation:

1. Node Class

This class represents a node in the AVL tree. Each node contains a key (value), references to its left and right children, and an integer height to maintain the height of the subtree rooted at this node. The height is used to maintain the balance of the tree.

2. getHeight Method

The getHeight method returns the height of a given node. If the node is null, it returns 0. This method is used to calculate the balance factor and to determine the height of the node during insertion and rotation operations.

3. getBalance Method

The getBalance method calculates the balance factor of a node by subtracting the height of the right subtree from the height of the left subtree. A balance factor of +1, 0, or -1 indicates that the node is balanced.

4. rotateRight Method

The rotateRight method performs a right rotation to restore balance in the AVL tree. This is typically done when the left subtree of a node is higher than the right subtree, causing the tree to be left-heavy.

5. rotateLeft Method

The rotateLeft method performs a left rotation to restore balance in the AVL tree. This is typically done when the right subtree of a node is higher than the left subtree, causing the tree to be right-heavy.

6. insert Method

The insert method inserts a new node into the AVL tree while maintaining its balance. After inserting the node, the tree is checked for balance using the getBalance method. If the tree is unbalanced, appropriate rotations are performed to restore balance.

7. preOrder Method

The preOrder method performs a pre-order traversal of the AVL tree, printing the key of each node. This method can be used to verify the structure of the tree after various operations.

Conclusion

This Java implementation of an AVL tree provides a self-balancing binary search tree that ensures O(log n) time complexity for insertion, deletion, and lookup operations. The AVL tree maintains its balance through rotations, ensuring efficient performance even in the worst-case scenarios.