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.

Binary search trees have very fast insertion and deletion when balanced, and the code is a lot simpler than other self balancing binary search trees.

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.txt · Last modified: 2015/02/02 08:28 (external edit)