CS131: Binary Search Tree

A binary search tree is a binary tree such that for any node n, if a node x is in n's left subtree, x's key is smaller than n's key nad if x is on the right subtree of n, x's key is bigger than n's key.

Fig: Binary Search Tree

From above figure let us consider the node with key 15. Its left subtree has nodes with keys 10,5 and 12, all of which are less than 15. Its right subtree has keys 20,17, and 22 all of which are bigger than 15. Node with same key can be in any subtree.

Binary search tree search for minimum or maximum key is fast and we can do inexact match like what is the largest key smaller than 57 and what is the smallest key bigger than 57. Or we can find a word with close but not exact spelling. While searching down the tree for a key k, if that key is not present we enclunter the node with smallest key greater that k and the node with largest key smaller than k.

If we do an inorder traversal we traverse the nodes in sorted order of the keys.

Operations

Min()

Start with root node and go to left child until no longer possible and return the last node encountered.

Max()

Start with root node and go to right child until no longer possible and return the last node encountered.

struct node
{
    int key;
    node *left, *right;
};

node* search(node root, int k, node* &parent)
{
    cur_node = root;
    while(cur_node != NULL)
    {
        if(cur_node->key == k)
        {
            return cur_node;
        }

        parent = cur_node;

        if(cur_node->key > k)
        {
            cur_node = cur_node->right;
        }
        else
        {            
            cur_node = cur_node->left;
        }
    }
    return NULL;
}

Insert(k):

Remove(k)

Find the node n with key k.
If none found return.
If n has no child remove it.
If n has one child replace n with its child.
If n has two children
  - Find node d with smallest key from n's right subtree
  - Remove remove d from its location and place at n's location

Example

Fig: Binary search tree

Remove(15)

Node 15 has two children and smallest key on the right subtree is 17. We replace node 15 with node 17 and the tree becomes:

Fig: Binary search tree after removing 15

remove(node root, int k)
{
    node* parent;
    node* target_node = search(root, k, parent)

    if(node == NULL)
    {
        return;
    }

    if(node->right == NULL && node->left == NULL)
    {
        if(parent->left == target_node)
        {
            delete target_node;
            parent->left = NULL;
        }

        if(parent->right == target_node)
        {
            delete target_node;
            parent->right = NULL;
        }
    }

    //todo
}

Running time

Running time for operations on a binary search tree depends on the depth of the tree. If the tree is balanced the depth of the tree oi O(log n) where n is the number of nodes in the tree. In that case the complexity of the operations is O(log n).

So, if the tree has O(log n) depth all operations takes O(log n)

But it is possible that the tree is not balanced. If we inser items in a binary search tree in sorted order the binary search tree becomes a linked list which will have a running time of O(n) for all operations. This is worst case running time.

Worst case complexity O(n)