Understanding AVL Trees

AVL trees are a type of self-balancing binary search tree named after their inventors Adelson-Velsky and Landis. They maintain a crucial property known as "balance factor" for each node. This balance factor represents the difference in height between the left and right subtrees of a node. The balance factor can be one of three values: -1, 0, or 1, indicating whether the tree is balanced or which side needs rebalancing.

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

1. Each tree has a root node (at the top)
2. The root node has zero, one, or two child nodes
3. Each child node has zero, one, or two child nodes
4. Each node has up to two children
5. 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 sub-trees cannot be more than one. This difference is called the balance factor.

The height of any node in an AVL tree is denoted as the number of edges between the node and the furthest leaf node.

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), where n is the number of nodes in the tree. The worst case space complexity is O(n).

Balance Factor

The balance factor in AVL trees is a crucial concept that determines the balance and overall structure of the tree. It is defined as the difference in height between the left and right subtrees of a node. Mathematically, the balance factor (BF) of a node is calculated as follows:

Bf = Height of left subtree - Height of right subtree

The balance factor can take one of three possible values:

• 0: If the balance factor of a node is zero, it means that the heights of its left and right subtrees are equal, or they differ by at most one. In other words, the node is considered balanced.
• -1: A balance factor of -1 indicates that the right subtree is taller than the left subtree by one level.
• 1: Conversely, a balance factor of 1 indicates that the left subtree is taller than the right subtree by one level.

AVL trees enforce a balance factor constraint to ensure that the absolute value of the balance factor for every node in the tree is at most 1. This constraint guarantees that the tree remains balanced, preventing it from degenerating into a structure with poor time complexity for operations like insertion, deletion, and searching.

Balancing AVL Tree

Balancing in the context of AVL trees refers to the process of ensuring that the tree maintains a specific balance criterion to optimize performance. In AVL trees, this balance is achieved by maintaining a balance factor for each node, which represents the difference in height between the left and right subtrees of that node. The balance factor can have one of three values: -1, 0, or 1.

The goal of balancing theory is to keep the balance factor of every node in the AVL tree within the range of [-1, 1]. When a node violates this balance criterion (i.e., its balance factor is outside this range), rotations are performed to restore balance while preserving the binary search tree property.

There are four main types of rotations used in AVL trees to restore balance:

1. Left-Left Rotation (LL): This rotation is applied when a node's balance factor becomes greater than 1 due to insertion or deletion in the left subtree of the left child. It involves a single right rotation to restore balance.
2. Right-Right Rotation (RR): The opposite of LL rotation, RR rotation is performed when a node's balance factor becomes less than -1 due to insertion or deletion in the right subtree of the right child. It entails a single left rotation to restore balance.
3. Left-Right Rotation (LR): LR rotation is used when a node's balance factor becomes greater than 1 due to insertion or deletion in the right subtree of the left child. It consists of a combination of left rotation followed by a right rotation to restore balance.
4. Right-Left Rotation (RL): The opposite of LR rotation, RL rotation is applied when a node's balance factor becomes less than -1 due to insertion or deletion in the left subtree of the right child. It involves a combination of right rotation followed by a left rotation to restore balance.

Basic AVL Tree Example

Consider the following sequence of numbers to insert into the AVL tree: 10, 5, 15, 3, 7, 12, 17.

We'll start with an empty AVL tree and insert each number one by one, ensuring that the tree remains balanced after each insertion.

1 Insert 10:

     10

The tree is balanced with only one node.

2 Insert 5:

     10
    /
   5

Since the balance factor of the root node (10) is 1 and the balance factor of its left child (5) is 0, the tree remains balanced.

3 Insert 15:

     10
    /  \
   5    15

The balance factors of nodes 10 and 5 are 0, and the balance factor of node 15 is 0, so the tree remains balanced.

4 Insert 3:

      10
    /   \
   5     15
  /
 3

The balance factor of node 10 is 2, and the balance factor of its left child (5) is 1. This violates the AVL property. To restore balance, we perform a right rotation on node 10:

     5
    / \
   3   10
       \
       15

5 Insert 7:

     5
    / \
   3   10
      / \
     7   15

The balance factors of all nodes are 0, so the tree remains balanced.

6 Insert 12:

     5
    / \
   3   10
      / \
     7   15
        /
      12

The balance factor of node 10 is 2, and the balance factor of its right child (15) is 1. This violates the AVL property. To restore balance, we perform a left rotation on node 10:

     5
    / \
   3   12
      / \
     10  15
    /
   7

Now, the tree is balanced again.

7 Insert 17:

     5
    / \
   3   12
      / \
     10  15
        / \
       7   17

The balance factors of all nodes are 0, so the tree remains balanced.

Complexity Analysis

1 Insertion:

• In the worst case, insertion into an AVL tree requires traversing from the root to the leaf level, which takes O(log n) time, where n is the number of nodes in the tree.
• After insertion, rebalancing operations may be required, which involve rotations. Rotations take constant time since they involve a fixed number of pointer adjustments.
• Therefore, the overall time complexity of insertion in AVL trees is O(log n).

2 Deletion:

• Similar to insertion, deletion involves traversing from the root to the leaf level, which also takes O(log n) time in the worst case.
• After deletion, rebalancing operations may be necessary, similar to insertion. These operations also take O(log n) time.
• Thus, the overall time complexity of deletion in AVL trees is O(log n).

3 Searching:

• Searching in an AVL tree also requires traversing from the root to the leaf level, taking O(log n) time in the worst case.
• Since AVL trees are binary search trees, searching involves comparing the search key with the keys of nodes during traversal, which has constant time complexity.
• Therefore, the overall time complexity of searching in AVL trees is O(log n).

4 Rotation Operations:

• Rotation operations (left rotation, right rotation, double rotation) are local operations that take constant time since they involve only a fixed number of pointer adjustments.
• Thus, the time complexity of rotation operations is O(1).

5 Traversal:

• Traversal operations, such as inorder, preorder, and postorder traversal, visit every node in the tree.
• In AVL trees, since each node is visited once, the time complexity of traversal operations is linearly proportional to the number of nodes in the tree, O(n), n is the number of nodes.
• Regardless of the specific traversal order (in-order, pre-order, post-order), visiting each node once requires O(1) time per node.
• Therefore, the overall time complexity of traversal in AVL tree is O(n).

In this table:

• n represents the number of nodes in the AVL tree.
• The complexities for insertion, deletion, and searching are logarithmic, O(log n), due to the balanced nature of AVL trees.
• Traversal operations have a linear complexity of O(n) because they visit each node once.
• Rotation operations have a constant complexity of 
  O(1) since they involve a fixed number of pointer adjustments.