Extended Visitors Example - Self-balancing Trees 

Balanced Trees

Binary Search Trees (BST's) are great for storing data and give us great speed...or do they?

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.  (See the quick refresher on "Big-O" analysis of programs.)
3. Worst case scenario for an unbalanced tree is O(n) behavior.

One really wants BSTs and other trees to be balanced for optimal performance!

2-3-4 Trees / B-Trees

Kind of like an n-ary tree but with multiple pieces of data on each tree root (node).

An extension of the idea of a BST where the ordering of the data in the child trees depends on the data in the parent node.

• See the PowerPoint Presentation!   (PDF -- no animations, MP4 -- no sound)
• See the OOPSLA 2002 Poster! (>740KB PNG file!)
• Read the OOPSLA 2002 paper in PDF format!
• See the demo!
• Traditional 2-3-4 algorithms
  • Compare the above demo to a demo of the traditional algorithms.    Here is the one of the clearest explanations of the traditional insertion and deletion algorithms from Prof. Neli Zlatereva at Central Connecticut State Univ.
  • For comparison:  quickie explanation of rotations
  • https://algorithmtutor.com/Data-Structures/Tree/2-3-4-Trees/
  • https://www.geeksforgeeks.org/2-3-trees-search-and-insert/

Additional materials:

• Deletion algorithm:
  • Switch statement based algorithm
  • Command based algorithm

Take-away

The main points of this discussion, besides teaching you about 2-3-4 and B-trees, is for you to see the following in action:

• How stepping back and re-assessing a traditional and "well understood" model leads to greater understanding of the system plus a simplified solution.
• How having a large number of cases does not imply that there are a large number of distinguishable cases.
• How extended visitors can make short work of complex problems by easily handling large numbers of cases.
• How commands can be used to dynamically capture a situation (environment) whose information is to be used at a later time.
• How the technique of "candidate data" can be used to abstract a search into process that minimizes the amount of calculations at any given step.

© 2020 by Stephen Wong