COMP 202: Principles of Object-Oriented Programming II ←  Design for Self-Balancing Trees  →

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   (with less animation)  
4. OOPSLA 2002 materials
   1. Paper in PDF format
   2. Poster (>740KB PNG file!)

URL: http://www.clear.rice.edu/comp202/08-fall/lectures/balanced/index.shtml
Copyright © 2008-2010 Mathias Ricken and Stephen Wong