A high balanced tree, also known as an AVL tree, is a self-balancing binary search tree in data structure. It was named after its inventors, Adelson-Velsky and Landis.
The main objective of a high balanced tree is to maintain a balance between the left and right subtrees. This balance ensures that the tree remains efficient for searching, inserting, and deleting elements.
Why Balance Matters
When we insert or delete nodes in a binary search tree, the tree’s structure can become skewed or unbalanced. A skewed tree has one subtree significantly larger than the other, which leads to inefficient operations. For example, searching for an element in a skewed tree may require traversing through many unnecessary nodes.
A balanced tree ensures that the height of its left and right subtrees differ by at most 1 level. By maintaining this balance, operations like search, insert, and delete can be performed efficiently with a time complexity of O(log n), where n is the number of nodes in the tree.
Properties of High Balanced Trees
A high balanced tree has the following properties:
- Height Balance: The height difference between left and right subtrees of any node is at most 1.
- Binary Search Tree Property: For every node x, all keys in its left subtree are smaller than x’s key, and all keys in its right subtree are greater than x’s key.
How High Balanced Trees Maintain Balance
To maintain balance during insertions and deletions, high balanced trees use rotations. A rotation is an operation that preserves the binary search property while adjusting the balance factor of nodes.
A left rotation is performed when the right subtree of a node becomes larger than the left subtree. This rotation moves the node down and to the left, making the left subtree larger and the right subtree smaller.
To perform a left rotation:
- Set the node’s right child as its new parent.
- Make the former parent the new left child of this new parent.
- Update pointers accordingly.
A right rotation is performed when the left subtree of a node becomes larger than the right subtree. This rotation moves the node down and to the right, making the right subtree larger and the left subtree smaller.
To perform a right rotation:
- Set the node’s left child as its new parent.
- Make the former parent the new right child of this new parent.
The Balance Factor
The balance factor of a node in a high balanced tree is defined as the difference in height between its left and right subtrees. It can have three possible values:
- +1: Indicates that the left subtree is taller by one level compared to its right subtree.
- -1: Indicates that the right subtree is taller by one level compared to its left subtree.
- 0: Indicates that both subtrees have equal height or that it is a leaf node (no children).
The balance factor helps determine if a tree needs rebalancing after an insertion or deletion operation. If any node’s balance factor becomes greater than 1 or less than -1, it means the tree is unbalanced and requires rotation to restore balance.
A high balanced tree is a self-balancing binary search tree that maintains balance by using rotations. It ensures efficient operations by keeping the height difference between left and right subtrees at most 1. By understanding the properties and rotation operations of a high balanced tree, you can implement and utilize this data structure effectively in your applications.