Data Structures & Algorithms Lecture Notes

12 November 2010 • 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

• Using data from any leaf 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).
  • A linked list is still a binary tree.
  • 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.

---

This page last modified on 16 November 2010.