In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree remains intact, with $k$ children you still have any of the $k!$ insertion sequences to rebuild the children into a new subtree since any legal BST among the children will work.

Is there a survey article on BST deletion algorithms? Most articles simply talk about the standard textbook BST delete algorithm.

  • 1
    $\begingroup$ I don't think there's a survey, but check out the Ralf Hinze paper "A fresh look at binary search trees" from 2002. Google will fix you up with a copy. $\endgroup$ – Pseudonym Jan 14 '14 at 6:02
  • $\begingroup$ Thanks. Hinze's paper also references Anderson's 1991 paper 'A note on searching in a binary search tree', user.it.uu.se/~arnea/ps/searchproc.pdf $\endgroup$ – Chad Brewbaker Jan 14 '14 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.