2-3-4 Trees Continued

Ambient Temperature: 72.9oF

Concepts

  1. 2-3-4 Tree Powerpoint, slides 18 -> 20
  2. When implementing a self-balancing 2-3-4 tree (or any complex data structure, for that matter), think before you code. Take the time to devise solutions that decouple interfaces from implementation, and that separate the variant and invariant behaviors. When applying code to those solutions, again take the time to plan a solution that takes full advantage of the high-level interfaces and abstractions that you have set up.
  3. The exhaustive exposition of 2-3-4 tree implementation attempts to make the above point by presenting a concrete example that exhibits all of the desired qualities: Yes, you could have an insert(…), delete(…), etc method on the tree’s class, but that limits the tree’s behaviors to the few that you personally define. By instead providing an accept(TreeVisitor …) method, you are creating a tree that can perform arbitrary behaviors. If you wish to include some “out of the box” behaviors (like insert, delete, etc), you could either provide wrapper methods or a visitor factory. However, once you admit the visitor pattern into your data structure, it is inconsistent and likely inconvenient to maintain non-visitor algorithms (like a traditional delete(…) method) alongside visitor algorithms.
  4. This level of abstraction is absolutely necessary in large projects with multiple groups of developers, so you need to get comfortable with if you plan to ever get paid for producing code.
  5. Short preview of HW06 provided code: The visitor pattern was used to create the parser for the ABC music language. None of that is code that we’ll have to read or modify.

Quotes

  1. “We don’t have any servers at all. We just have Macbooks and beef jerky.” – Siegfried Bilstein, EGraphs
  2. “I have an anonymous inner class inside an anonymous inner class, and I’m gonna have another anonymous inner class inside of here…” – Dr. Wong

Resources

  1. 2-3-4 Tree Powerpoint: http://www.clear.rice.edu/comp310/f12/lectures/lec21/DP4SBT.ppt

This entry was posted on October 15, 2012 at 1:12 pm and is filed under Lectures. Tagged: , , , . You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.