SUNY Geneseo Department of Computer Science

Ordered Binary Trees

{Date}

CSci 141, Fall 2004
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Questions?

Ordered Binary Trees

Reading summary: Sections 13.3.1 and 13.3.2

Definition of "ordered" that's not positional
- Defined relative to root and children
- Tree is in order if root and child pairs satisfy requirement
Requirement: left subtree contains values less than root, right subtree contains values bigger than root
Algorithms to traverse tree visiting every node once
Connection between traversal and order?
- Traversal visits nodes in ascending order
- Order in tree enables traversal to quickly visit nodes in ascending order
  - "Quick" = Θ(n)
  - n = number of items in tree

Traversal Time

    traverse
        if ! this.isEmpty()
            this.getLeft().traverse()
            visit root
            this.getRight().traverse()

A more rigorous derivation of the execution time of the "traverse" algorithm
Based on count of primitive tree operations
Count left and right separately
Count operations in terms of number of nodes in tree
Recurrence relation:
- f(n) = 1 if n = 0
- f(n) = 3 + f(n1) + f(n2) if n > 0
- Where n1 + n2 = n-1
- n1 = number of nodes on left
- f(n1) = messages sent to process left
- n2 = number of nodes on right

[Trees with Traversal Visiting Subtree]

Look for a pattern

n = 0	f(n) = 1
n = 1	f(1) = 3 + f(0) + f(0)
	= 3 + 1 + 1
n = 2	f(2) = 3 + f(1) + f(0)
	= 3 + (3+1+1) + 1
n = 3	f(3) = 3 + f(1) + f(1)
	= 3 + (3+1+1) + (3+1+1)
	or 3 + f(2) + f(0)
	= 3 + 3+(3+1+1)+1 + 1

Hmm ... f(n) = 4n + 1?

Prove f(n) = 4n + 1
- By strong induction on n
- Base case, n = 0
  - f(0) = 1 from recurrence
  - = 4 * 0 + 1
- Induction hypothesis: assume f(x) = 4x + 1 for all 0 <= x < k
- Show f(k) = 4k + 1
  - f(k) = 3 + f(k1) + f(k2) from recurrence
    - where k1 + k2 = k-1; 0 <= k1, k2 < k
  - = 3 + 4(k1) + 1 + 4(k2) + 1 from induction hypothesis
  - = 3 + 4(k1+k2) + 1 + 1
  - = 3 + 4(k-1) + 1 + 1
  - = 4k + 1
So f(n) = 4n + 1 = Θ(n)

Next

Building and searching ordered trees

Read Sections13.3.3 and 13.3.4