AVL Trees are a type of self-balancing binary search tree, where the heights of the two child subtrees of any node differ by at most one. When an insertion or deletion operation causes this balance to be violated, rotations are performed to restore it. There are four types of rotations used in AVL Trees:
Right Rotation: This is applied when a node becomes unbalanced due to a left-heavy subtree. The right rotation involves making the left child the new root of the subtree and adjusting the pointers accordingly.
Left Rotation: This is the opposite of the right rotation and is used when a node becomes unbalanced due to a right-heavy subtree. Here, the right child becomes the new root of the subtree.
Left-Right Rotation: This is a double rotation that combines a left rotation followed by a right rotation. It is used when a left child has a right-heavy subtree.
Right-Left Rotation: Another double rotation that combines a right rotation followed by a left rotation, which is applied when a right child has a left-heavy subtree.
These rotations help to maintain the balance factor, defined as the height difference between the left and right subtrees, ensuring efficient operations on the tree.
Start your personalized study experience with acemate today. Sign up for free and find summaries and mock exams for your university.