Maggie HTTN
Case Study • Data Structures

B-tree Deletion Logic

Developing a rule-based learning system to streamline decision-making and structural reasoning in complex tree rebalancing.

B-tree deletion introduces multiple repair cases that often create significant barriers for learners. This module restructures the algorithm into a decision-driven framework, utilizing high-fidelity visualization and predictive logic to bridge the gap between theory and implementation.

The project demonstrates how targeted instructional sequencing can manage high intrinsic cognitive load while maintaining technical rigor.

Watch Demo

Project Scope

Curricular Target
Upper-division Data Structures and Algorithms coursework.
Delivery Model
Hybrid instructional module; adaptable for synchronous lecture or asynchronous self-study.
Learner Profile
Computer Science students transitioning from basic insertion logic to complex structural repair.
Primary Objective
Enable students to accurately diagnose underflow and select optimal repair strategies.

Core Learning Outcomes

  • Diagnose underflow conditions and identify violated structural invariants.
  • Analyze sibling capacity to select the appropriate repair (Borrow vs. Merge).
  • Execute internal-node deletion via predecessor/successor substitution.
  • Evaluate root-level changes and justify height reduction scenarios.

The Instructional Challenge

B-tree deletion presents a high degree of branching logic that often leads to cognitive overload. The primary hurdle is not the deletion itself, but the secondary "repair" decisions required to maintain tree balance, where students frequently lose track of parent-child key relationships.

Design Strategy & Pedagogical Approach

Rule Abstraction
Condensed textbook complexity into four repeatable, high-level decision rules: Replace, Borrow, Merge, Shrink.
Visual Externalization
Transformed abstract "underflow" thresholds into visual cues, allowing learners to focus on strategy rather than mental arithmetic.
Scaffolded Decision-Making
Reframed deletion as a logic-gate sequence ("Which rule applies?") to build reliable procedural mental models.
Active Schema Formation
Integrated prediction prompts that require learners to justify their rule choice before the animation reveals the result.

Solution Architecture: Engineering the Learning Path

The module was engineered to move learners from passive observation to active structural diagnosis by making "hidden" algorithmic mechanics visible.

1. Invariant Diagnosis

The visualization highlights the violated (t − 1) invariant immediately upon deletion. This forces the learner to recognize the "Problem State" before attempting a "Repair State."

2. Visual Substitution Logic

Internal key deletions are modeled as substitutions rather than removals. By showing the motion of predecessor/successor keys, the tool clarifies why recursive repair is necessary.

3. Kinetic Separator Movement

During Borrow and Merge operations, parent keys are animated moving *down* through the levels. This transparency prevents the misconception that keys are simply deleted and recreated.

4. Recursive Propagation Modeling

The animation explicitly demonstrates how structural repairs can ripple upward to the root, providing a holistic understanding of tree rebalancing that static diagrams cannot offer.

Evaluation & Iteration:

Testing revealed initial learner confusion regarding the "Borrow vs. Merge" threshold.

The design was iterated to include active sibling-capacity labeling and reduced transition speeds during separator shifts. These refinements significantly improved the accuracy of learner predictions during formative check-ins.

Interactive Implementation

The resulting animation functions as a structured model for rule selection and structural stabilization.

Watch actively: pause, predict the next step, and decide which rule applies.

This implementation demonstrates the full lifecycle of a B-tree, from internal key replacement to root-level height reduction.

Guided Worksheet (Pause & Predict)

This worksheet is designed to support active learning during the animation. Pause the video at each step, predict what will happen next, then continue to check your understanding.

Step Example

Before watching the next step:

  • Which rule do you think will apply next? (Borrow / Merge / Replace)
  • Why do you think this rule is correct?
  • What do you expect will change in the tree?

After watching:

  • What actually happened?
  • Was your prediction correct? Why or why not?

Repeat this process for each step in the animation. Focus on understanding the decision-making process rather than memorizing steps.

Assessment Strategy

This module evaluates understanding through both guided practice and short assessment questions focused on decision-making.

  • Formative assessment (during learning): Guided prompts help students practice choosing the correct rule and explaining their reasoning.
    • Which rule applies in this step — Borrow or Merge?
    • What condition tells you this rule is correct?
    • What will change in the tree after applying this rule?
  • Application assessment (structure + process): Students demonstrate understanding by tracking how the tree changes step-by-step.
    • Which key moves from the parent during this operation?
    • How do the child nodes change after the operation?
    • Does the change affect higher levels of the tree?
  • Summative assessment (after learning): A short exit check confirms whether students can independently apply the rules.
    • When do we choose Borrow instead of Merge?
    • Why do we replace a key before deleting from an internal node?
    • What condition causes the tree height to shrink?

Assessment Integration

  • Strategic prediction prompts for rule selection.
  • Sketch-and-justify exercises for rebalancing.
  • Exit-ticket focus on decision logic and invariant maintenance.

Inclusive Design

  • Explicit labeling to reduce cognitive search and support working memory.
  • Non-color reliant cues for invariant violations (WCAG compliance).
  • Scaffolded worksheets for diverse learning preferences.

Instructional Impact

The module successfully shifts student focus from memorizing code to understanding structural invariants, resulting in higher accuracy when justifying repair strategies during complex deletion scenarios.