Data Structures and Algorithms Lecture Notes

28 March 2011 • Binary Search Trees

---

Outline

• Motivation
• Tree properties.
• Extension and details.

Tree Performance

• Search has O(n) behavior.
• Add has O(1) behavior.
• Remove has O(n) behavior.
• This is not what we paid for.
• There’s not enough information in the tree to move through it intelligently.
• How to add more information? Sorting!

Binary Trees and Order

• Go back to the original list and assume it’s in order.

  

• Now make a tree out of it.

  

• What properties do such a tree show?

Binary Search Trees

• A binary tree T obeys the binary search property if, for every node n in T,
  • every node in n’s left subtree contains a value less than n.v and
  • every node in n’s right subtree contains a value at least n.v.
• A binary tree obeying the binary search property is a binary search tree.

Example

Every left subtree L contains values less than the value at L’s root, and

• Every right subtree R contains values at least the value at R’s root.

Binary Search Tree Member

bool member(T e, node root)
  if root = nil, return false
  if root.data = e, return true
  if e < root.data
    return member(e, root.left)
  return member(e, root.right)

Binary Search Tree Add

• It’s easiest to add new data as a leaf.

  node * add(T e, node * root)
    if root = nil
      root = new node(data, nil, nil)
    or e < root.data
      root.left = add(e, root.left)
    or
      root.right = add(e, root.right)
    return root
  

Removing Nodes.

• Diving down to any leaf value will remove a value in a binary tree.

  

• Does the same algorithm work when removing a value from a binary search tree?

Removing Nodes..

• Using data from any leaf may not work.

  

• The BST property requires the largest value on the left or the smallest on the right.

Binary Search Tree Remove

Node remove(V v, Node root)

 if (root != null)
   if v < root.value
    root.left = remove(v, root.left)
   else if root.value < v
    root.right = remove(v, root.right)
   else
    if root.left != null
     root.left, root.value = extractMax(root.left)
    else if root.right != null
     root.right, root.value = extractMin(root.right)
    else
     root = null

 return root

See the code.

Performance

• Has worst-case performance improved for operations on binary search trees?
• Sadly, no: they are still O(n).
  • A linked list is still a binary tree.

    

  • The binary search property is some of the machinery needed for O(log n) behavior.
  • More to come...

Summary

• Binary search trees generalize sorted linked lists.
• But why aren’t binary search trees faster than lists?
  • Lists have the same performance at lower implementation costs.

References

• Binary Search Trees, Section 10.1, in Data Structures & Algorithms in Java, fifth ed., by Michael Goodrich and Roberto Tamassia.
• Ternary Search Trees by Jon Bentley and Robert Sedgewick, Dr Dobb’s Journal, April 1998.
• A Note on Searching in a Binary Search Tree by A. Andersson in Software—Practice and Experience, October, 1991.

---

This page last modified on 2010 November 16.