Exercise #6 (cont)
Cost analysis:
- similar to cost for inserting keys in random order O(log2N)
- does not rely on keys being supplied in random order
Approach can also be applied to deletion:
- standard method promotes inorder successor to root
- for the randomised method ...
- promote inorder successor from right subtree, OR
- promote inorder predecessor from left subtree
- choice depends on relative sizes of subtrees (favours larger)
|