gen-briefly-explain-a-balanced-tree-rotation-and-one-common-misc-1e45

Briefly explain a balanced tree rotation and one common misconception about it.

# Balanced Tree Rotation ## Brief Explanation A tree rotation is a local restructuring operation that changes the tree's shape while preserving the binary search tree property (left < parent < right). It involves "pivoting" around an edge between a parent and child node, promoting the child up and demoting the parent down. **Example of a right rotation:** ``` y x / \ / \ x C → A y / \ / \ A B B C ``` Rotations are used in self-balancing trees (AVL, Red-Black) to maintain logarithmic height after insertions/deletions. ## Common Misconception **"Rotations are expensive operations."** Many people assume rotations are costly because they seem to involve restructuring large portions of the tree. In reality, **rotations are O(1) operations** that only modify a constant number of pointers (typically 3-6), regardless of tree size. The confusion arises because people conflate the cost of *finding where* to rotate (which involves traversal) with the rotation itself. The rotation operation is just pointer reassignment—very cheap.