Binary Search Trees

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. When inserting or searching for an element in a binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found.

Wikipedia

Important Definitions

Binary Tree: A tree that starts at a single root and branches down, all nodes have a minimum of 0 children (leaves) and a maximum of 2 children.
Complete Binary Tree: All levels are full except at the bottom level, all levels are filled left to right.
Full Binary Tree: All nodes have 2 children or 0 children (leaf).
Binary Search Tree: A binary tree with the Search Tree Property.
Search Tree Property: For any node x, all nodes in it’s left subtree are less than x and all nodes in its right subtree are greater than or equal to x.

Binary Search Tree Algorithms

def search(key, node):
     if node is None or node.key == key:
         return node
     if key < node.key:
         return search(key, node.left)
     else:
         return search(key, node.right)
def insertion:
    - Search and insert where we fell off tree
def find_min(node):
       if node.left is None:
           return node
       else:
           return find_min(node.left)
def find_max(node):
       if node.right is None:
           return node
       else:
           return find_max(node. right)
def successor(node):
         if node.right:
             return find_min(node.right)
         else:
             Go up until you find a node with it's parent on the right, return parent
def delete(node):
         if node is leaf:
            delete node
         if node has one child:
            connect node parent to node child
            delete node
         if node has 2 children:
            swap node with successor(node)
            delete (node)

Runtime Complexity
Search: O(h)
Insert: O(h)
Find Min: O(h)
Find Max: O(h)
Successor: O(h)
Delete: O(h)
h can range from
O( log (n) ) – Best Case, Balanced BST
O(n) – Worst Case, Linked List BST

Leave a Reply

Your email address will not be published. Required fields are marked *