<p>In helping out @bapi-chatterjee on a <a href="https://cstheory.stackexchange.com/questions/20533/height-of-randomly-built-binary-search-tree-by-insert-and-delete">BST question</a> , 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.</p>

<p>Is there a survey article on BST deletion algorithms? Most articles simply talk about the <a href="http://en.wikipedia.org/wiki/Binary_search_tree#Deletion" rel="nofollow noreferrer">standard textbook BST delete algorithm</a>.</p>

CC BY-SA 3.0
2014-01-14T06:02:07.543Z
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
CC BY-SA 3.0
2014-01-14T17:45:53.430Z
Thanks. Hinze's paper also references  Anderson's 1991 paper 'A note on searching in a binary search tree', http://user.it.uu.se/~arnea/ps/searchproc.pdf
Chad Brewbaker
<ds.data-structures><combinatorics>
Binary Search Tree DELETE survey
Chad Brewbaker
# Binary Search Tree DELETE survey

(Asked by: username_0 on 2014-01-13)

In helping out @bapi-chatterjee on a [BST question](https://cstheory.stackexchange.com/questions/20533/height-of-randomly-built-binary-search-tree-by-insert-and-delete) , 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](http://en.wikipedia.org/wiki/Binary_search_tree#Deletion).

**Tags:** ds.data-structures, combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks. Hinze's paper also references  Anderson's 1991 paper 'A note on searching in a binary search tree', http://user.it.uu.se/~arnea/ps/searchproc.pdf  

---

## 0 answers

