Tree Balancing: AVL Trees

4.1 Problems with Unbalanced Trees

When adding elements to regular (unbalanced) trees, you can run into some annoying issues.

1. Increased tree height:

In unbalanced trees, the height can reach n (where n is the number of nodes), leading to degraded performance.

The time for basic operations (search, insert, delete) becomes O(n) in the worst case.

2. Uneven node distribution:

In unbalanced trees, some subtrees might have lots more nodes than others, leading to inefficient memory use and longer processing times.

3. Worse operation time:

Operations like searching, inserting, and deleting take longer in unbalanced trees because of the increased tree height.

Example of an unbalanced tree:

In this example, the tree basically turns into a linked list, and operation times become linear.

4.2 Defining an AVL Tree and Its Properties

An AVL tree (named after its inventors, Adelson-Velsky and Landis) is a type of balanced binary search tree where for any node, the height difference between its left and right subtrees is at most 1.

Properties of AVL Tree:

1. Balance:

The height difference between the left and right subtrees of any node is at most 1.

This ensures tree height of O(log n), where n is the number of nodes, guaranteeing efficient search, insert, and delete operations.

2. Binary Search Tree:

An AVL tree has all the properties of a binary search tree: for any node, all keys in the left subtree are less than the node's key, and all keys in the right subtree are greater.

3. Automatic Balancing:

After every insert or delete operation, the tree is rebalanced to maintain its properties.

4.3 Examples of Tree Balancing

Rotations are operations done to restore balance in an AVL tree after inserting or deleting nodes. There are four types of rotations: left, right, left-right, and right-left.

1. Left Rotation:

In a left rotation, node x moves up, and its right child y becomes its parent. y's left subtree becomes x's right subtree.

2. Right Rotation:

In a right rotation, node x moves up, and its left child y becomes its parent. y's right subtree becomes x's left subtree.

3. Left-Right Rotation:

First, perform a left rotation on the left child node, then a right rotation on the node itself.

4. Right-Left Rotation:

First, perform a right rotation on the right child node, then a left rotation on the node itself.

4.4 Basic Operations in AVL Trees

Basic operations in AVL trees include insertion, deletion, and search.

Insertion

You need to insert a new node into the AVL tree and rebalance it if needed.

Steps:

1. Insert the node:
   • Start at the tree root and recursively find the right spot for the new node by comparing its value with the current nodes.
   • Insert the new node in the found spot, just like in a regular binary search tree.
2. Update heights:
   • After insertion, update the heights of all nodes along the path from the new node to the root.
3. Rebalance the tree:
   • Check the balance of each node along the path from the new node to the root.
   • If any node's balance is off (the height difference of the left and right subtrees is more than 1), perform the appropriate rotation to restore balance.

Example:

2. Deletion

You need to delete a node from the AVL tree and rebalance it if needed.

Steps:

1. Find and delete the node:

• Start at the tree root and recursively find the node to delete.
• Delete the node just like in a regular binary search tree:
• If the node is a leaf, just remove it.
• If the node has one child, replace the node with its child.
• If the node has two children, find the smallest node in the right subtree (or largest in the left), copy its value to the node to be deleted, and recursively delete the smallest node in the right subtree.

2. Update heights:

• After deletion, update the heights of all nodes along the path from the deleted node to the root.

3. Rebalance the tree:

• Check the balance of each node along the path from the deleted node to the root.
• If any node's balance is off, perform the appropriate rotation to restore balance.

Example:

3. Search

You need to find a node with a given value in the AVL tree.

Steps:

1. Recursive search:

• Start at the tree root and recursively compare the search value with the current nodes.
• If the value is less than the current node, move to the left subtree.
• If the value is greater than the current node, move to the right subtree.
• If the value matches the current node, return that node.

Example: