Tuesday, 2 July 2013

Binary Search Trees

Binary Search Trees
  • A binary search tree is a binary tree T such that
    • each internal node stores an item (k,e) of a dictionary,
    • keys stored at nodes in the left subtree of node v are less than or equal to k(v), the key stored at node v,
    • keys stored at nodes in the right subtree of v are greater than or equal to k(v), and
    • external nodes do not store elements but rather serve as placeholders.


Search
  • The binary search tree T is a decision tree where the question asked at an internal node v is whether the search key k is less than, equal to, or greater than the key stored at v.
  • Pseudocode:
Algorithm TreeSearch(k,v): Input: A search key k and a node v of a binary search tree T.
Output: A node w of the subtree T(v) of T rooted at v, such that either w is an internal node storing key k or w is the external node encountered in the inorder traversal of T(v) after all the internal nodes with keys smaller than k and before all the internal nodes with keys greater than k.
if v is an external node then
return v
if k = key(v) then
return v
else if k < key(v) then
return TreeSearch(k, T.leftChild(v))
else // k > key(v)
return TreeSearch(k, T.rightChild(v))

Search (cont.)
  • Two search examples, one successful, the other unsuccessful.

Insertion into a Binary Search Tree


  • To perform the Dictionary operation insertItem(k,e) on a Dictionary implemented with a binary search tree,
    • Start by calling TreeSearch(k, T.root()) on T. Let w be the node returned by TreeSearch.
    • If w is external, we know that no item with key k is stored in T. We then call expandExternal(w) on T and have w store the item (k,e).
    • If w is internal, we know that another item with key k is stored at w. We call TreeSearch(k, T.rightChild(w)) iteratively, until an external node is returned.
  • The above algorithm eventually traces a path from the root of T down to an external node which gets replaced by an internal node that stores the new item.

Insertion into a Binary Search Tree (cont.)
  • Insertion of an element with key 78:
a)
b)

Insertion into a Binary Search Tree (cont.)
  • Insertion of an element with key 80:


Removal from a Binary Search Tree
Algorithm
  • Execute algorithm TreeSearch(k, T.root()) on T to find a node storing k in T.
  • if TreeSearch(k,T.root()) returns an external node, return the special object NO_SUCH_KEY.
  • else if w¬TreeSearch(k,T.root()) returns an internal node and one of the children of the internal node w storing the key is external:
    • z ¬ external child of w
    • replace w with the sibling of z (call removeAboveExternal(z))
  • else
    • Find the first internal node y that follows w in the inorder traversal of T. The left child x of y is the external node that immediately follows node w in the inorder traversal of T.
    • t ¬ element(w)
    • swap(y,w) {move element of y into w}
    • removeAboveExternal(x)
    • return t

Removal from a Binary Search Tree (cont.)
  • Removal where the key the remove is stored at a node (w) with an external child.

Removal from a Binary Search Tree (cont.)


Removal from a Binary Search Tree (cont.)
  • Removal where the key to remove is stored at a node whose children are both internal:

Removal from a Binary Search Tree (cont.)


Time Complexity
  • Searching, insertion, and removal in a binary search tree are all O(h), where h is the height of the tree.
  • On average, a binary search tree with n keys generated from a random series of insertions and deletions has expected height O(log n). This statement, however, requires precise mathematical language in the definition of "a random series of insertions and deletions."
  • However, in the worst case, the costs of searching, insertion, and removal are O(n) if the height of the tree is equal to n. Thus in some cases, searching, insertion, and removal is no better than in a sequence.

  •    
     
     
     
    Lafore Binary Search Tree Applet (not available on public version)
       
  • Thus, to prevent the worst case, we need to develop a rebalancing scheme to bound the height of the tree to O(log n).



 Class SimpleBinarySearchTree
Class SimpleBinarySearchTree
public class SimpleBinarySearchTree implements SimpleDictionary {
    Comparator C; // comparator
    BinaryTree T; // binary tree
    protected Position actionPos; // insertion position or parent of removed position
    public SimpleBinarySearchTree(Comparator c) {
        C = c;
        T = (BinaryTree) new BTNodeBinaryTree();
    }     // auxiliary methods:
    protected Object key(Position position) {
        return ((Item) position.element()).key();
    }
    protected Object element(Position position) {
        return ((Item) position.element()).element();
    }

Class SimpleBinarySearchTree (cont.)
    protected void checkKey(Object key) throws InvalidKeyException {
        if(!C.isComparable(key))
            throw new InvalidKeyException("Key "+key+" is not comparable");
    }     protected Position findPosition(Object key, Position pos) {
        if (T.isExternal(pos))
            return pos; // key not found and external node reached returned
        else {
            Object curKey = key(pos);
            if(C.isLessThan(key, curKey))
                return findPosition(key, T.leftChild(pos));      // search in left subtree
            else if(C.isGreaterThan(key, curKey))
                return findPosition(key, T.rightChild(pos));      // search in right subtree
            else
                return pos; // return internal node where key is found
        }
    }

Class SimpleBinarySearchTree (cont.)
// method findAllVectorEnum omitted // methods of the dictionary ADT
publicint size() { return (T.size()-1)/2; }
publicboolean isEmpty() { return T.size() == 1; }
public Object findElement(Object key) throws InvalidKeyException {
    checkKey(key); // may throw an InvalidKeyException
    Position curPos = findPosition(key, T.root());
    actionPos = curPos;
    if (T.isInternal(curPos))
        return element(curPos);
    else
        return NO_SUCH_KEY;
}
// Method findAllElements omitted

Class SimpleBinarySearchTree (cont.)
publicvoid insertItem(Object key, Object element)
                                    throws InvalidKeyException {
    checkKey(key); // may throw an InvalidKeyException
    Position insPos = T.root();
    // if the insertion key already exists, insert the new
    //item to the right of all the existing items with the same key
    do {
        insPos = findPosition(key, insPos);
        if (T.isExternal(insPos))
            break;
        else
            insPos = T.rightChild(insPos);
        } while (true);
    T.expandExternal(insPos);
    Item newItem = new Item(key, element);
    T.replace(insPos, newItem);
    actionPos = insPos;
}



Class SimpleBinarySearchTree (cont.)
public Object remove(Object key) throws InvalidKeyException {
    Object toReturn;
    checkKey(key); // may throw an InvalidKeyException
    Position remPos = findPosition(key, T.root());
    if(T.isExternal(remPos)) {
        actionPos =remPos;
        return NO_SUCH_KEY;
    }
    else{
        toReturn = element(remPos); // element to be returned
        if (T.isExternal(T.leftChild(remPos)))
            remPos = T.leftChild(remPos);
        else if (T.isExternal(T.rightChild(remPos)))\
            remPos = T.rightChild(remPos);
        else { // key is at a node with internal children
            // find node for swapping items
            Position swapPos = remPos;
            remPos = T.rightChild(swapPos);
            do
                remPos = T.leftChild(remPos);
            while (T.isInternal(remPos));
            swap(swapPos, T.parent(remPos));
        }
        actionPos = T.sibling(remPos);
        T.removeAboveExternal(remPos);
        return toReturn;
    }
}
    // Methods omitted: removeAll, keys, elements, swap
    // Also omitted: private methods
}
 Class BTNodeBinaryTree

AVL Trees
  • An AVL tree is a binary search tree that satisfies the height-balance property: for every internal node v of T, the heights of the children of v can differ by at most 1.
  • The height-balance property requires additional rules on the structure of the binary search tree to guarantee O(log n) height.
  • An immediate consequence of the height-balance property is that any subtree of an AVL tree is itself an AVL tree.
  • AVL stands for Adel’son, Vel’skii and Landis.
  • An example of an AVL tree where the heights are shown next to the nodes:

Height of an AVL Tree
  • Proposition: The height of an AVL tree T storing n keys is O(log n).
  • Justification: The easiest way to approach this problem is to try to find the minimum number n(h) of internal nodes of an AVL tree of height h.
    • Two base cases:
      • n(1) = 1.
      • n(2) = 2.

Height of an AVL Tree (cont.)
    • For n ³ 3, an AVL tree of height h minimally contains the root node, one AVL subtree of height h-1 and the other AVL subtree of height h-2.
                                 (1)



Height of an AVL Tree (cont.)
Note that (1) implies that
                 (2)
for any integer i such that h-2i³ 1. For base cases, pick h-2i=1 and h-2i=2 because we know that n(1)=1 and n(2)=2. For the base case h-2i=1 we have i=(h-1)/2 and for the base case h-2i=2 we have i=(h-2)/2. Thus solving for m, the maximum value of i, we have
since
.

Height of an AVL Tree (cont.)
Returning now to equation (2) and replacing i with m,
Therefore,
,
which yields the desired result
.

Insertion into an AVL Tree
  • A binary search tree T is considered balanced if for every node v in T, the heights of v’s children differ by at most 1.
  • Since an AVL tree is a binary search tree, inserting a node into an AVL tree involves performing an expandExternal(w) operation on T, which changes the heights of some of the nodes in T, including w.
  • If an insertion causes T to become unbalanced, we travel up the tree from the newly created node until we find the first node x such that its grandparent z is an unbalanced node. Only nodes on the path from w to the root node are candidates for becoming unbalanced.
  • Since z became unbalanced by an insertion in the subtree rooted at its child y,
height(y) = height(sibling(y)) + 2
  • To rebalance the subtree rooted at z, we must perform a restructuring

Restructuring
  • In pseudo-code:
Algorithm restructure(x): Input: A node x of a binary search tree T that has both a parent y and a grandparent z.
Output: Tree T restructures by a rotation (either single or double) involving nodes x, y, and z.
    1. Let (a,b,c) be an inorder listing of the nodes x, y, and z, and let (T0, T1, T2, T3) be an inorder listing of the four subtrees of x, y, and z not rooted at x, y, or z.
    2. Replace the subtree rooted at z with a new subtree rooted at b.
    3. Let a be the left child of b and let T0 and T1 be the left and right subtrees of a, respectively.
    4. Let c be the right child of b and let T2 and T3 be the left and right subtrees of c, respectively.

Example of Insertion into an AVL Tree

 
 


Restructuring Illustrated
  • There are four ways to rotate nodes in an AVL tree. Each is graphically represented here.
    • Single rotations (when b = y):
      • rotating y over z.




Restructuring Illustrated (cont.)
    • double rotations (when b = x):
      • Rotating x over y and then over z.


Removal from an AVL Tree
  • Start by executing the remove method on a generic binary search tree. This requires a call to removeAboveExternal.
  • We can easily see that performing a removeAboveExternal(w) can cause T to become unbalanced.
  • Let z be the first unbalanced node encountered while traveling up the tree from w. Also, let y be the child of z with the larger height, and let x be the child of y with the larger height.
  • We perform the operation restructure(x) to restore balance at the subtree rooted at x.
  • As this restructuring may upset the balance of another node higher up in the tree, we must continue checking for balance until the root of T is reached.
  • Each restructure operation is O(1). Therefore removal is O(log n).

Removal (cont.)
  • Example of deletion from an AVL tree:


Removal (cont.)
  • Another example of deletion from an AVL tree:


 Class AVLItem
Class AVLItem
public class AVLItem extends Item {
    int height;
    public AVLItem(Object k, Object e, int h) {
        super(k, e);
        height = h;
    }
    public int height() {
        return height;
    }
    public int setHeight(int h) {
        int oldHeight = height;
        height = h;
        return oldHeight;
    }
}

 Class SimpleAVLTree
Class SimpleAVLTree
public class SimpleAVLTree extends SimpleBinarySearchTree implements SimpleDictionary {
    public SimpleAVLTree(Comparator c) {
        super(c);
        T = new RestructurableNodeBinaryTree();
    }
    private int height(Position p) {
        if(T.isExternal(p))
            return 0;
        else
            return ((AVLItem) p.element()).height();
        }
    private void setHeight(Position p) { // called only if p is internal
        ((AVLItem)p.element()).setHeight(1+ Math.max(height(T.leftChild(p)),
                    height(T.rightChild(p))));
    }

Class SimpleAVLTree (cont.)
privateboolean isBalanced(Position p) {
    // test whether node p has balance factor between - // 1 and 1
    int bf = height(T.leftChild(p)) –
    height(T.rightChild(p));
    return ((-1 <= bf) && (bf <= 1));
} private Position tallerChild(Position p) {
    // return a child of p with height no smaller than that
    // of the other child
    if(height(T.leftChild(p)) >= height(T.rightChild(p)))
        return T.leftChild(p);
    else
        return T.rightChild(p);
    }



Class SimpleAVLTree (cont.)
// dictionary methods
publicvoid insertItem(Object key, Object element) throws InvalidKeyException {
    super.insertItem(key, element);// may throw an
    // InvalidKeyException
    Position zPos = actionPos; // start at the insertion position
    T.replace(zPos, new AVLItem(key, element, 1));
    rebalance(zPos);
} public Object remove(Object key) throws InvalidKeyException {
    Object toReturn = super.remove(key); // may throw
    // an InvalidKeyException
    if(toReturn != NO_SUCH_KEY) {
        Position zPos = actionPos; // start at the removal position
        rebalance(zPos);
    }
return toReturn;
}

Class SimpleAVLTree (cont.)
privatevoid rebalance(Position zPos) {
    // traverse the path of T from zPos to the root; for each node encountered,
    //recompute its height and perform a rotation if it is unbalanced
    while (!T.isRoot(zPos)) {
        zPos = T.parent(zPos);
        setHeight(zPos);
        if (!isBalanced(zPos)) { // perform a rotation
            Position xPos = tallerChild(tallerChild(zPos));
            zPos = ((RestructurableNodeBinaryTree)T).restructure(xPos);
            setHeight(T.leftChild(zPos));
            setHeight(T.rightChild(zPos));
            setHeight(zPos);
        }
    }
}
}  Class RestructurableBinaryTree
Interface java.util.SortedMap
Class java.util.TreeMap