Data Structures & Algorithms Lecture Notes

1 December 2009 • 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.

  

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.e and

  • every node in n’s right subtree contains a value at least n.e.

• A binary tree obeying the binary search property is a binary search tree.

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

• Using data from a child may not work.

  

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

Binary Search Tree Remove

node * remove(node * r)

  if r.left ≠ nil
    r.left = remove_max(r.left, r.data)

  or r.right ≠ nil
    r.right = remove_min(r.right, r.data)

  or
    delete r
    r = nil

  return r

Performance

• Has worst-case performance improved for operations on binary search trees?

• Sadly, no: they are still O(n).

  • The binary search property is only part of the machinery needed to insure 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.