Tree rotation
A tree rotation is a local restructuring operation that changes parent-child relationships while preserving the in-order sequence of a binary search tree.
Advanced Algorithms and Data Structures
A tree rotation is a local restructuring operation that changes parent-child relationships while preserving the in-order sequence of a binary search tree.
- How it is used
- Repairs treap priority violations during insertion and deletion without disturbing binary-search-tree key order.
- How deep it goes
- Works through both rotation directions and their pointer updates, then applies repeated rotations to treap insertion and deletion.
- Examples
- Uses an inventory insertion that rotates a new leaf upward and a deletion that rotates an entry down to a leaf.
- What you can do after
- Build it from scratch by reconnecting parent and child links for left or right rotation, including a possible root change.
Read how Advanced Algorithms and Data Structures explains tree rotation →
Grokking Algorithms, Second Edition
A tree rotation is a local restructuring operation that changes parent-child relationships while preserving the tree's ordering.
- How it is used
- Balances AVL trees after insertions make their height depart from the desired logarithmic bound.
- How deep it goes
- Demonstrates left rotations and balance-factor updates, but defers the other rotation cases and implementation details.
- Examples
- Uses three-node A/B arrangements and growing AVL trees containing 20, 30, and 10.
- What you can do after
- Apply rotations to rebalance an AVL tree and preserve logarithmic search and insertion performance.
Read how Grokking Algorithms, Second Edition explains tree rotation →
Related concepts
- treapused by · A treap is a randomized binary search tree whose nodes satisfy both binary-search-tree ordering by key and heap ordering by priority.
- AVL treeused by · An AVL tree is a self-balancing binary search tree that maintains bounded differences between subtree heights through rotations.
- heap invariantcontrasts with · A heap invariant is the ordering constraint requiring each node's value or priority to be properly ordered relative to its parent or children.
- binary search treeuses · A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.
- right rotationincludes · A right rotation is a binary-search-tree rotation in which a node's left child becomes the root of the rotated subtree.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.