Sean Bollin
Reputation: 910
Find the node whose deletion requires 2 rotations?
Draw an AVL tree with 8 keys 1,...,8.
For the tree find a node whose deletion requires 2 rotations.
When I draw the tree I don't see any nodes where a deletion would require 2 rotations. Am I wrong?
Upvotes: 0
Views: 49
Answers (1)
alw
Reputation: 56
An AVL tree does not have to be unique given a certain set of keys for example, the same set of keys could generate an AVL tree with 8 at 7's current position with a left pointer to 7. Considering this tree and looking at http://en.wikipedia.org/wiki/AVL_tree#Insertion, you should be able to find a node such that deleting it would lead to a Right Left case.
Upvotes: 2
Related Questions
- AVL Rotation - Which node to rotate
- AVL tree delete
- AVL Tree rotation order
- In AVL-Tree, why needs more one performance of rotation in deletion?
- AVL tree worst case number of rotations during insertion and deletion
- AVL tree rotating techniques?
- AVL Tree Rotation's
- What is the minimum sized AVL tree where a deletion causes 2 rotations?
- What additional rotation is required for deletion from a Top-Down 2-3-4 Left-leaning Red Black tree?
- Regarding AVL rotations