rotation
A small local rearrangement of a search tree that lifts a child above its parent while keeping the keys in order.
In more detail
A left rotation fixes a right-heavy node and a right rotation a left-heavy one; a double rotation is two single ones in opposite directions, for zig-zag shapes. Each rotation rewires a constant number of pointers, so it is O(1). The in-order sequence of keys is unchanged, so the BST property survives.
Related terms
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
- balance factor — For a tree node, the height of its left subtree minus the height of its right subtree.
Taught in
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers