**This is an old revision of the document!**

A binary search tree is a binary tree data structure where each node is greater than all the nodes in its left sub-tree and smaller than all the nodes in its right sub-tree. Each child is another binary search tree.

The shape of a binary search tree depends on the order of insertions and it can be degenerate. More complex data structures like AVL-trees or red-black trees are self balancing binary search trees and ensure that the shape does not become degenerate leading to worst case run times.

Average | Worst case | |
---|---|---|

Space | $O(n)$ | $O(n)$ |

Search | $O(\log n)$ | $O(n)$ |

Insert | $O(\log n)$ | $O(n)$ |

Delete | $O(\log n)$ | $O(n)$ |

binary_search_tree.1405831810.txt.gz · Last modified: 2015/02/02 08:24 (external edit)