Tree's Rotation

Why we need to learn rotation

Rotation is an operation used to balance the tree structure. Its main purpose is to optimize the depth of the tree and thus improve the efficiency of search, insertion, and deletion operations.BST rotation is divided into left-handed and right-handed, and its specific uses are as follows:

• Reduce the height of the tree: Rotation can adjust the BST into a more balanced structure, avoiding the appearance of a chain (like a linked list) structure, thereby reducing the height of the tree. For example, if the tree becomes a one-sided tilted structure (i.e. highly unbalanced) after inserting a node, it can be rebalanced through rotation, shortening the search path and improving the efficiency of the operation.
• Improve search efficiency: A balanced BST has a lower height, so the average search complexity is lower (O(log n)), and has better search performance than an unbalanced tree. In a highly unbalanced tree, the worst-case search complexity degenerates to O(n).
• Implementing self-balancing trees: Rotation is the core operation for implementing self-balancing binary trees. For example, in self-balancing trees such as AVL trees and red-black trees, rotation is frequently used to maintain the balance condition, thus ensuring that the time complexity of all basic operations is O(log n).

Specific operation of rotation

• Right Rotation
• Left Rotation

Ratation Diagram

tree rotation simulator

if you want to see the animation of rotation in AVL tree, visit the tree rotation simulator.