Lecture on Binary Tries

Introduction

• Binary tries: Treat sequences as binary strings.
• Immutable data structure: Outer class with internal nodes.
• Elements: Referred to as vectors.

Components of Binary Tries

• Array-based structure: Fundamental component.
• Two types of nodes:
  • Leaf nodes: Store data.
  • Internal nodes: Store other nodes.

Example Walkthrough

• Grouping by twos for simplicity.
  • Typical: 32 bits integer results in 8 tree levels when grouped by fours.

Adding Elements

1. Start with an empty vector: Array size zero.
2. First addition: Creates a new vector, V1, with one element.
3. Subsequent additions:

• V2: New leaf with two elements (A, B).
• V3: New leaf with three elements (A, B, C).
• V4: Leaf node with four elements (full capacity).

4. Next addition:

• V5: Transition to internal nodes when leaf is full.
• Creates an internal node with pointers to existing and new leaf nodes.

5. Further additions: Continued use of new internal nodes.

• V6: Updates pointers, adding new elements efficiently without changing previous nodes.
• V7, V8: Follow similar pattern by creating new internal nodes and leaves as needed.
• V9: Represents compact representation with new levels.

Implementation Details

• Data storage in leaves: Array of element type (e.g., Array<E>).
• Internal nodes:
  • Store array of vector type elements (Vector of either leaves or internal nodes).
  • Track level to know the amount of downshifting needed (level x group size).
• Helpful conventions: Use hexadecimal representation for clarity (e.g., 0x3 for binary treatment).

Next Steps

• Upcoming lecture will cover coding these operations.