SUNY Geneseo Department of Computer Science

Performance of Ordered Binary Tree Search/Insert

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

"What's the Point of a CS Major?" panel

Current student, faculty, alumnus discussing what they see as the reasons for/value in studying CS as an undergraduate
Audience questions/statements
Pizza, soda, mingling
Thursday Apr. 12, 12:45 - 2:00
South 309
RSVP to me or Cathy Taylor

GREAT Day

Tuesday, April 17, all day
Student presentations on research, art work, similarly scholarly activities
Including 4 or 5 posters on student research in CS -- what you could be doing in a year or so
See http://www.geneseo.edu/CMS/display.php?page=5155&dpt=great for summary schedule

Questions?

Efficiency of Binary Tree Algorithms

Section 13.3.5

Execution time for searching and insertion depends on height
Bunch of proofs
- About fully balanced trees and their heights
- All by induction on tree height
- Recursive definition of fully balanced
  - Empty tree is fully balanced
  - Each subtree is empty or has 2 (fully balanced) children of equal height
- Conclusion: relationship betwen number of nodes, n, and height, h is....
  - h = log₂(n+1)
Therefore
- Search time in fully balanced tree of n nodes is Θ(logn)
- Insertion time in fully balanced tree of n nodes is Θ(logn) (single element)
- Construction time for fully balanced tree of n nodes is Θ(n logn) (n insertions into initially empty tree)
  - Really sum 1 + 2*2 + 4*3 + ... + n/2*log₂(n)
  - Book approximates by noting that sum is at least n/2 log₂(n) = Ω(n logn)
  - Plus terms totalling < n/2 log₂n
  - So total is no more than n/2 log₂(n) + n/2 log₂n = n log₂n
What sort of tree matters
- Fully balanced vs plain balanced (almost fully balanced)
Totally unbalanced trees are rare in real life
Fully balanced
- Number of nodes depends on height and vice versa
Search and construction time

What are the factors that influence execution time? Which measure problem size, and which are secondary influences determining best vs worst cases for a given problem size?

Factors
- Height
  - Best case: h = log₂(n+1)
  - Worst case: h = n
- Number of nodes - problem size
- Location in tree
  - Best case: root, time = Θ(1)
  - Worst case: leaf, time = Θ(h)

Hand out Problem Set 12

Deletion from an ordered binary tree.

Read Section 13.5.1

Next Lecture