[prev] [index] [next]

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)