Randomised BST Insertion (cont)
Cost analysis:
- similar to cost for inserting keys in random order: O(log2 n)
- 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
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}