David J Nevin+= Code

Last updated: Jun 27, 2022

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.

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

100
101
102
103
104
105
106
107
108
109
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)
Algorithm Average Case Worst Case
Search O(logn) O(n)
Insert O(logn) O(n)
Delete O(logn) O(n)

note:

100
101
102
103
104
| 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


Next: Site Projects June 19th
Previous: Level Order Traversal Binary Tree