Binary Search Tree

Definition#

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

Search#

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.

Time Operation#

If the tree is non-linear the search time is O(logn) and in the worst case where the tree is linear, O(n).

Implementation#

class Node(object):
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None


class BST(object):
  def __init__(self, root):
    self.root = Node(root)

note:

| Algorithm | Average Case | Worst Case |
| :-------: | :----------: | :--------: |
|  Search   |  O(_logn_)   |    O(n)    |
|  Insert   |  O(_logn_)   |    O(n)    |
|  Delete   |  O(_logn_)   |    O(n)    |

source: Markdown: How to Create a Table