What fundamental tree operation is used by AVL trees and Red-Black trees to restore balance after an insertion or deletion?
Show answer
Rotation
Rotations (left or right) are local operations that change the structure of the binary search tree while preserving the in-order traversal property. They are used to decrease the height of skewed subtrees.
Also asked as:
- Which local tree operations are performed by self-balancing binary search trees like AVL and Red-Black trees to decrease the height of skewed subtrees?