CODEWITHSUNDEEP
data-structurestreebinary-search-treeavl-tree
jielouis341
jielouis341

Reputation: 1

AVL Tree rotation order

When there is an Imbalance and a Rotation is needed in an AVL tree, how do you go about picking which nodes to rotate first. In examples, sometimes I see the root node gets rotated first, sometimes I see a parent node get rotated first and sometimes a leaf node gets rotated first.

Upvotes: 0

Views: 331

Answers (1)

trincot
trincot

Reputation: 350147

With AVL trees, the imbalance caused by an insertion or deletion of a leaf will be detected as the balance factors are updated along the path from the leaf to root. As soon as a node is found (in that upwards traversal) that gets a balance factor that is out of range, either a single or double rotation will happen at that node. However, a double rotation breaks down into two single rotations, and the first of these two really acts on a child of the given node.

Upvotes: 1

Related Questions