B-Tree with Splay Optimization

Features

  • ✓ Configurable N-way branching (min degree ≥ 2)
  • ✓ Splay-like node promotion for hot data
  • ✓ Thread-safe operations with mutexes
  • ✓ Real-time async operations with callbacks
  • ✓ Interactive macOS GUI visualization
make && ./BTreeVisualizer

Complexity

  • Search: O(log n)
  • Insert: O(log n)
  • Delete: O(log n)
  • Space: O(n)
View Proofs

Dynamic N-Way Splay Tree

Rsync Optimized

  • ✓ Dynamic N-way branching (2 to N, adaptive)
  • ✓ Full splay operations (Zig, Zag, Zig-Zig, etc.)
  • ✓ Rolling checksums (Adler-32 variant)
  • ✓ Block metadata and matching
  • ✓ Real-time visualization with access counts
make splay && ./NSplayTreeVisualizer

Complexity

  • Search: O(log n) amortized
  • Insert: O(log n) amortized
  • Delete: O(log n) amortized
  • Space: O(n)
View Proofs

Circular Buffer Splay Tree

Features

  • ✓ Fixed-size circular buffer for memory efficiency
  • ✓ Self-adjusting splay tree operations
  • ✓ Multiple sorting modes (lexicographic, numeric, semantic)
  • ✓ Ascending and descending sort support
  • ✓ LRU eviction policy when buffer is full
  • ✓ Thread-safe operations with mutex locks
#include "CircularBufferSplayTree.h"

Complexity

  • Search: O(log n) amortized
  • Insert: O(log n) amortized
  • Delete: O(log n) amortized
  • Sort: O(n) or O(n·k) for variable keys
  • Space: O(bufferSize)
View Proofs

Sorting Modes

📝 Lexicographic

String-based alphabetical comparison for text data

🔢 Numeric

Standard numeric comparison for integer/float keys

🧠 Semantic

Custom comparison function for domain-specific ordering

Interactive Visualizations

Nodes: 0
Height: 0
Operations: 0

Complexity Analysis

Operation B-Tree N-Way Splay Tree Circular Buffer Splay Space
Search O(log n) O(log n) amortized O(log n) amortized O(n)
Insert O(log n) O(log n) amortized O(log n) amortized
Delete O(log n) O(log n) amortized O(log n) amortized
Sort (Asc/Desc) O(n) O(n) O(n) or O(n·k)
Sort Modes - - Lex/Num/Sem
📚 View All Mathematical Proofs 📄 View Markdown Summary

About

This project implements high-performance tree data structures with multithreaded operations and real-time GUI visualization for macOS.

Copyright (C) 2025, Shyamal Suhana Chandra. All rights reserved.

Technology Stack

C++ Objective-C TypeScript JavaScript Canvas API Jekyll GitHub Pages