User Tools

Site Tools


Differences

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

Link to this comparison view

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)