# Binary Search Tree DELETE survey

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.

• 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. – Pseudonym Jan 14 '14 at 6:02
• 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 – Chad Brewbaker Jan 14 '14 at 17:45