Binary Search Tree

Binary Search Tree

  • A binary search tree is a binary tree storing keys (or key-element pairs) at its internal nodes and satisfying the following property:
    • Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v. We have key(u) ≤ key(v) ≤ key(w)
    • External nodes do not store items
  • An inorder traversal of a binary search trees visits the keys in increasing order
  • Performance:
    • Consider a dictionary with n items implemented by means of a binary search tree of height h
      • the space used is O(n)
      • methods findElement, insertItem and removeElement take O(h) time
    • The height h is O(n) in the worst case and O(log n) in the best case
  • Binary search performs operation findElement(k) on a dictionary implemented by means of an array-based sequence, sorted by key
    • similar to the high-low game
    • at each step, the number of candidate items is halved
    • terminates after a logarithmic number of steps
  • To search for a key k, we trace a downward path starting at the root
  • The next node visited depends on the outcome of the comparison of k with the key of the current node
  • If we reach a leaf, the key is not found and we return NO_SUCH_KEY
  • Example: findElement(4)
Algorithm findElement(k, v)
  if T.isExternal (v)
    return NO_SUCH_KEY
  if k < key(v)
    return findElement(k, T.leftChild(v))
  else if k = key(v)
    return element(v)
  else { k > key(v) }
    return findElement(k, T.rightChild(v))

Insertion

  • To perform operation insertItem(k, o), we search for key k
  • Assume k is not already in the tree, and let let w be the leaf reached by the search
  • We insert k at node w and expand w into an internal node
  • Example: insert 5

Deletion

  • To perform operation removeElement(k), we search for key k
  • Assume key k is in the tree, and let let v be the node storing k
  • If node v has a leaf child w, we remove v and w from the tree with operation removeAboveExternal(w)
  • Example: remove 4
  • We consider the case where the key k to be removed is stored at a node v whose children are both internal we find the internal node w that follows v in an inorder traversal
  • we copy key(w) into node v
  • we remove node w and its left child z (which must be a leaf) by means of operation removeAboveExternal(z)
  • Example: remove 3