Binary Search Trees

Overview#

Binary Search Tree (BST) is a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.

Example:

8
/ \
3 10
/ \
1 6

Tree Operations#

Basic Operations#

  • Search: If less, go left. If more, go right. If equal, search hits.
  • Insert: If less, go left. If more, go right. If null, insert new element.
  • Get: Same as search, return value corresponding to the key. Else, return null if key not found.
  • Put: Perform search. If key in tree, reset value. Else, add new node.
  • Hibbard Deletion: To delete a node with key k, search for node t with key k
    • Case 0: If t has 0 children, delete t by setting parent link to null
    • Case 1: If t has 1 child, delete t by replacing parent link to t's child link.
    • Case 2: If t has 2 children,
      • Find successor x of t
      • Delete minimum in t's right subtree
      • Put x in t's spot

We insert new elements into a BST by comparing the values of the right and left nodes. We traverse until we find an empty spot (i.e. the child is None).

Similarly, for search, we keep comparing the search key to current node's value to determine whether to search on the right or left sub-tree.

Ordered Operations#

  • Min: Smallest key: Keep going left from root
  • Max: Largest key: Keep going right from root
  • Ceil: Smallest key >= given key
  • Floor: Largest key <= given key
    • Case 1: k equals key in node, where k is the given key
    • Case 2: k is less than key in node: floor(k) is in left subtree
    • Case 3: k is larger than key in node: floor(k) is in right subtree if there is any key <= k. Else, it is the key in the node.
  • Rank: How many keys are < k?
  • Select: Given a rank, what is the key which yields this rank?

Time Complexity of Operations#

  • Search: Average of O(log n), Worst of O(n)
  • Insert: Average of O(log n), Worst of O(n)
  • Delete: Average of O(log n), Worst of O(n)

The worst case occurs when we have a linear BST. For example, if we insert a sorted or reverse sorted list of elements, we end up with a linear tree. In a way, this becomes like a linked list.

Implementation#

Tree Node#

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

BST#

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

Insert Node#

def insert(self, val):
self.__insert(self.root, val)
def __insert(self, curr, val):
if(val < curr.data):
if curr.left:
self.__insert(curr.left, val)
else:
curr.left = Node(val)
else:
if curr.right:
self.__insert(curr.right, val)
else:
curr.right = Node(val)

Search Tree#

def search(self, val):
return __search(self.root, val)
def __search(self, curr, val):
if curr is None:
return False
if(val == curr.data):
return True
elif val > curr.data:
return self.__search(curr.right, val)
else:
return self.__search(curr.left, val)

The above can also be implemented iteratively.