Binary Search Trees

1.  Binary Search Tree:

    a)  Definition : A BST is a binary tree in symmetric order.

         A binary tree is either:

         -- Empty.

         -- Two disjoint binary trees (left and right).

    b)  Symmetric order: Each node has a key, and every node’s key is:

         -- Larger than all keys in its left subtree.

         -- Smaller than all keys in its right subtree.

 

2.  Java definition: A BST is a reference to a root Node.

 

private class Node
{
    private Key key;
    private Value val;
    private Node left, right;
    public Node(Key key, Value val)
    {
        this.key = key;
        this.val = val;
    }
}

 

 

3.  Search:

    a) If less, go left; if greater, go right; if equal, search hit.

    b) Cost : Number of compares is equal to 1 + depth of node.

    c) Java Implementation :

 

public Value get(Key key)
{
    Node x = root;
    while (x != null)
    {
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x = x.left;
        else if (cmp > 0) x = x.right;
        else if (cmp == 0) return x.val;
    }
    return null;
}

 

 

4.  Put:

    a)  If less, go left; if greater, go right; if equal, update value; if null, insert

    b)  Cost : Number of compares is equal to 1 + depth of node.

    c)  Java Implementation :

 

public void put(Key key, Value val)
{ 
    root = put(root, key, val); 
}

private Node put(Node x, Key key, Value val)
{
    if (x == null) return new Node(key, val);
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        x.left = put(x.left, key, val);
    else if (cmp > 0)
        x.right = put(x.right, key, val);
    else if (cmp == 0)
        x.val = val;
    return x;
}

 

 

5.  Tree shape :

    a)  Many BSTs correspond to same set of keys.

    b)  Tree shape depends on order of insertion.

 

6.  Correspondence between BSTs and quicksort partitioning : Correspondence is 1-1 if array has no duplicate keys.

 

7.  Mathematical Analysis : 

    a)  If N distinct keys are inserted into a BST in random order, the expected number of compares for a search/insert is ~ 2 ln N. (1-1 correspondence with quicksort partitioning.)

    b)  If N distinct keys are inserted in random order, expected height of tree ( the longest path) is ~ 4.311 ln N.

    c)  Worst-case height is N when keys are inserted in ascending order.

 

8.  Ordered Operations:

    a)  Minimum : most left key

    b)  Maximum : most right key

    c)  Floor : Largest key ≤ a given key k:

        1)  k equals the key at root -- The floor of k is k.

        2)  k is less than the key at root -- The floor of k is in the left subtree.

        3)  k is greater than the key at root -- The floor of k is in the right subtree (if there is any key ≤ k in right subtree); otherwise it is the key in the root.

        4)  Java Implementation :

        

public Key floor(Key key)
{
    Node x = floor(root, key);
    if (x == null) return null;
    return x.key;
}

private Node floor(Node x, Key key)
{
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null) return t;
    else return x;
}

    d)  Ceiling : Smallest key ≥ a given key k. ( similar to Floor )

 

    e)  Size of Subtree :  In each node, we store the number of nodes in the subtree rooted at that

node:

 

private class Node
{
    private Key key;
    private Value val;
    private Node left;
    private Node right;
    private int count;
}

public int size()
{ 
    return size(root); 
}

private int size(Node x)
{
    if (x == null) return 0;
    return x.count;
}

private Node put(Node x, Key key, Value val)
{
    if (x == null) return new Node(key, val);
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = put(x.left, key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else if (cmp == 0) x.val = val;
    x.count = 1 + size(x.left) + size(x.right);
    return x;
}

     f)  Rank. How many keys < k

 

 

public int rank(Key key)
{ 
    return rank(key, root); 
}

private int rank(Key key, Node x)
{
    if (x == null) return 0;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) return rank(key, x.left);
    else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
    else if (cmp == 0) return size(x.left);
}

 

 

9.  Inorder Tranversal

    a)  traverse left subtree; enqueue key; traverse right subtree.

    b)  Inorder traversal of a BST yields keys in ascending order.

    c)  Java Implementation : 

 

public Iterable<Key> keys()
{
    Queue<Key> q = new Queue<Key>();
    inorder(root, q);
    return q;
}

private void inorder(Node x, Queue<Key> q)
{
    if (x == null) return;
    inorder(x.left, q);
    q.enqueue(x.key);
    inorder(x.right, q);
}

 

 

10. Deletion:

    a)  lazy approach : 

        1)  Set the value of node to be deleted to null.

        2)  Leave key in tree to guide searches (but don't consider it equal in search).

        3)  Cost : ~ 2 ln N' per insert, search, and delete (if keys in random order), where N' is the number of key-value pairs ever inserted in the BST.

        4)  Unsatisfactory solution: Tombstone (memory) overload.

    b)  Deleting Minimum:

        1)  Go left until finding a node with a null left link.

        2)  Replace that node by its right link.

        3)  Update subtree counts.

        4)  Java Implementation :

 

public void deleteMin()
{ 
    root = deleteMin(root); 
}

private Node deleteMin(Node x)
{
    if (x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.count = 1 + size(x.left) + size(x.right);
    return x;
}

     c)  Hibbard Deletion :

        1) [0 children] Delete t by setting parent link to null.

        2) [1 child] Delete t by replacing parent link.

        3) [2 children] Find successor x of t. Delete the minimum x in t's right subtree.Put x in t's spot.

        4) Java Implementation:

public void delete(Key key)
{ 
    root = delete(root, key); 
}

private Node delete(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = delete(x.left, key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else {
        if (x.right == null) return x.left;
        if (x.left == null) return x.right;
        Node t = x;
        x = min(t.right);
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    x.count = size(x.left) + size(x.right) + 1;
    return x;
}

        5) Unsatisfactory solution: Not symmetric. Trees not random (!) ⇒ sqrt (N) per op.