SUNY Geneseo Department of Computer Science

Introduction to Binary Trees

Previous Lecture

Questions?

A Data Structure for Searching

Theta(n) search time for lists is really pretty bad

Can we devise a data structure that supports faster searches?

Consider how you would look something up in, e.g., a dictionary or telephone book

• Split into categories, e.g., 26 groups by initial letter, start search in right group for word you want
• Continue this scheme for other letters, i.e., put data into alphabetical order

Generalize this...

• Based on check for greater-than/less-than
  • Compare data you seek to middle item
  • If data is less than middle, repeat in first half
  • If data greater than middle, repeat in second half
• "Divide and conquer"

Binary Tree

• Recursive data structure consisting of...
  • Object (root) and two smaller trees (subtrees), or
  • Empty
• Binary Search Tree
  • Binary tree and
  • Everything in left subtree < root
  • Everything in right subtree > root
  • Left and right subtrees are binary search trees

Operations on (binary) trees - tree messages

• boolean isEmpty()
• Object root()
• BinaryTree left()
• BinaryTree right()
• constructor() [make empty tree]
• constructor( Object root, BinaryTree left, BinaryTree right) [make non-empty tree]

Searching a binary search tree

1. compare data you seek to root
2. if data equals root, stop
3. if data is less than root, repeat in left subtree
4. if data greater than root, repeat in right subtree

Mini-assignment: phrase search w/ tree messages

Next Lecture