Algorithm

Avl Tree Visualization     An AVL Tree is a special type of Binary Search Tree that automatically keeps itself balanced. A normal Binary Search Tree can provide very fast searching, insertion, and deletion when the tree remains balanced. In that situation, these operations can take O(log n) time. However, a normal Binary Search Tree does not automatically control its shape. If we insert values in a certain order, the tree can become very tall. When that happens, the tree can start behaving like a linked list, and searching can take O(n) time. An AVL Tree solves this problem by checking its balance after every insertion and deletion. When the tree becomes unbalanced, it changes its structure using rotations. In this article, we will learn how AVL Trees work, why we need them, how to calculate their balance factor, how rotations work, and how to implement an AVL Tree in C++. What Is a Binary Search Tree? Before understanding an AVL Tree, we need to understand a Binary Search Tree. A Binary Search Tree, usually called a BST, stores values according to a simple rule. Every value in the left subtree must be smaller than the current node. Every value in the right subtree must be larger than the current node. For example: 50 / \ 30 70 / \ / \ 20 40 60 80 The root contains 50. Values smaller than 50 go to the left. Values larger than 50 go to the right. The same rule continues inside every subtree. For example, 30 has 20 on its left because 20 is smaller than 30. It has 40 on its right because 40 is larger than 30. This structure allows us to search efficiently. Suppose we want to find 60. We start at 50. Since 60 is greater than 50, we move to the right. We reach 70. Since 60 is smaller than 70, we move to the left. We reach 60. We found the value after checking only a few nodes. The Problem With a Normal Binary Search Tree A Binary Search Tree does not automatically balance itself. Suppose we insert these values in this order: 10 20 30 40 50 The tree can become: 10 \ 20 \ 30 \ 40 \ 50 This tree still follows all the rules of a Binary Search Tree. However, the structure is inefficient. The tree has almost become a linked list. If we search for 50, we have to visit: 10 → 20 → 30 → 40 → 50 If the tree contains one million nodes and has this shape, a search could require almost one million comparisons. The search time becomes O(n). A balanced tree gives us a much smaller height. For one million nodes, a balanced tree can have a height close to log₂(1,000,000), which is about 20. This means we can search through a very large collection while checking only a small number of levels. What Is an AVL Tree? An AVL Tree keeps the Binary Search Tree rules while also keeping the tree balanced. AVL stands for Adelson Velsky and Landis, the names of the researchers who introduced this data structure. The main rule is simple. For every node, the height difference between the left subtree and the right subtree must not be greater than 1. The tree checks this difference using something called the balance factor. If the tree becomes unbalanced, the AVL Tree performs a rotation to fix its structure. The AVL Tree therefore combines two important ideas: Binary Search Tree + Automatic balancing = AVL Tree What Is Height? Height tells us how many levels exist below a node. For our implementation, we use the following definition: Empty tree = 0 New node = 1 For example: 50 / \ 30 70 The nodes 30 and 70 have height 1. The node 50 has height 2. Now consider: 50 / 30 / 20 The node 20 has height 1. The node 30 has height 2. The node 50 has height 3. We calculate the height of a node using: height = 1 + maximum(left height, right height) The 1 represents the current node. What Is the Balance Factor? The balance factor tells us whether a node has a balanced structure. We calculate it using: Balance Factor = Height of Left Subtree − Height of Right Subtree Suppose a node has: Left height = 3 Right height = 2 Then: Balance Factor = 3 − 2 = 1 The node is balanced. Now suppose we have: Left height = 3 Right height = 1 Then: Balance Factor = 3 − 1 = 2 The node is now unbalanced. An AVL Tree allows these balance factors: −1 0 +1 When the balance factor becomes: −2 or: +2 the node needs rebalancing. Why Does an AVL Tree Need Rotations? When we insert a new value, we can make one side of the tree taller than the other side. For example: 30 / 20 / 10 The left side has become much taller than the right side. The balance factor of 30 is: 2 The tree needs to change its structure. We call this structural change a rotation. A rotation moves nodes around while keeping the Binary Search Tree ordering correct. AVL Trees use four main cases: Left Left Right Right Left Right Right Left Left Left Case Consider inserting: 30 20 10 The tree becomes: 30 / 20 / 10 The new value moved left from 30 and then left again from 20. This creates the Left Left case. The balance factor of 30 becomes +2. We fix the tree using a right rotation. Before the rotation: 30 / 20 / 10 After the rotation: 20 / \ 10 30 The tree becomes balanced. Right Right Case Now consider inserting: 10 20 30 The tree becomes: 10 \ 20 \ 30 The new value moved right from 10 and then right again from 20. This creates the Right Right case. The balance factor of