SUNY Geneseo Department of Computer Science

Ordered Trees

Previous Lecture

Misc

Making up the lost tests

• Repeat exam for those who want it (next Thursday, April 22)
• Those who don't want to take it can be graded just on 1st hour exam, final, labs, homework, and readings/mini-assignments, with
  • 1st hour exam worth 25%
  • Final worth 40%
  • Labs worth 20%
  • Rest per syllabus
• After the retest starts, you cannot change your mind about whether or not to take it.

End of semester info

• SOFI's next Tuesday (April 20)
  • Czar/czaritza?
• Final Thursday April 29, 12:00 Noon
  • Comprehensive but biased towards trees and limits of computation
  • Designed for 2 hours, you have 3
  • Open books, notes, computers
  • Same style qustions as hour exams
• Labs meet on Monday, April 26

Hand out Lab 13

Questions?

Lab: adding decisions

• Can code be copy of search except it asks for new question and answer?
• Yes, but don't copy code, better to use common method

Why does "println" on tree node print

• <<> foo <<> bar<>>>....
• Shows recursive structure of tree
• That's what "toString" method produces
  • You can write your own

Derive maximum number of decisions tree can make

Add-questions method returns?

• 1. void, changes tree
• 2. returns new tree
• x.m().n() sends "n" message to the result returned by the "m" message

Ordered Tree Properties

Section 13.3

Ordered tree

• Everything on left less than root
• Everything on right greater than root

Traverse an ordered tree

• Look at left subtree
• Look at root
• Look at right subtree

Anything added to tree goes in leaf

• Done in kind of same way as traversal:
  • If less than root, add to left subtree
  • If greater than root, add to right subtree

Very efficient for searching

• Similar reasons to binary search -- can split into halves

Wording: "find does not search every node ... only those nodes in direct path"

• Except if tree degenerates to a list

Traversal is recursion, but different from search

• Traversal recursively processes both sides
• Search only processes one side

Why are searches so efficient?

• Tree has to be balanced
• Time (for balanced tree) of n nodes is Theta( log n )
• n = number of nodes
• h = height
• Lemmas lead to n = 2^h - 1
  • Solve for h: h = log₂(n+1)

Next

Limits of Computer Science

Read Chapter 17

Next Lecture