This shows you the differences between two versions of the page.

binary_search_tree [2014/07/19 21:50] will created |
binary_search_tree [2015/02/02 08:28] |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | ====== Binary search tree ====== | ||

- | 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. | ||

- | |||

- | ===== Properties ===== | ||

- | | ^ 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)$ | | ||

- | |||

- | [algorithm Binary search tree] |

binary_search_tree.txt ยท Last modified: 2015/02/02 08:28 (external edit)