Binary Search Tree
binary search tree (BST) is a tree data structure in which nodes are arranged according to the following property.
The value of the left child of any node will be less than whatever value in that node, and the value of the right child of the node will be greater than the value in that node.
If there aren’t exactly two children, the reference to the non-existent child will contain null value.
We employ the same criteria when searching. Starting form the
root we decide which branch to search by comparing the search value with the current node. We then traverse the appropriate branch and repeat the process, thus greatly speeding up the search.
If the tree is non-linear the search time is O(logn) and in the worst case where the
tree is linear, O(n).
|Algorithm||Average Case||Worst Case|
source: Markdown: How to Create a Table