Rice University - Comp 212 - Intermediate Programming

Spring 2008

Lecture #32 - Design Patterns for Self-balancing Trees - Insertion Algorithm

1. Why do we need balanced trees?
   1. Trees offer much faster access than lists, but only if the tree so long as all the branches are nearly the same length, i.e. "balanced".
   2. A balanced tree gives O(log n) behavior, while lists give O(n) behavior.  
   3. Worst case scenario for an unbalanced tree is O(n) behavior.
2. Demo code
   1. Pre-Java 5.0 JRE/SDK: 
      1. binaries in a jar file   (To run: java -jar NTree.jar)
      2. source code, zipped
   2. Post-Java 5.0-compatible JRE/SDK
      1. DrJava project
      2. Executable jar file  (To run: java -jar dp4sbt_jre50.jar)
3. PowerPoint Presentationn  
4. OOPSLA 2002 materials
   1. Paper in PDF format
   2. Poster (>740KB PNG file!)