Back to Data Structures

Tree Data-Structure Library

October 17, 2026 Wasil Zafar 18 min read

Implement BST, AVL, red-black, B-tree, and treap behind one ordered-map interface with invariant checkers.

Table of Contents

  1. Project Brief and API Contract
  2. Architecture and Data Flow
  3. Core Implementations in Python, C++, and Java
  4. Visual Walkthrough of the Engine
  5. Correctness Testing Against a Reference Oracle
  6. Benchmarks and Complexity Report
  7. Extensions and Stretch Goals

Project Brief and API Contract

The Tree Data-Structure Library is a production-grade, unified ordered-map engine that abstracts diverse self-balancing search tree backends—Unbalanced Binary Search Tree (BST), AVL Tree, Red-Black Tree, Treap, and B-Tree—behind a clean, language-agnostic interface. In modern database engines, key-value stores, and file systems, ordered maps require distinct performance trade-offs: low-latency lookup vs. rapid insertion, memory compactness vs. cache-friendly node fan-out. This library isolates these implementations behind a single abstract contract while incorporating real-time structural invariant checkers to guarantee algorithmic correctness after every mutation.

The public interface defines core dictionary operations (put, get, remove, contains, range_query) alongside an explicit validation engine (validate_invariants). Every backing tree structure must comply with strict operational semantics and pass automated differential testing against language-standard reference oracles (std::map in C++, TreeMap in Java, and dict/sortedcontainers in Python).

Tree Library API Contract: The library must expose a unified OrderedMap interface accepting key-value pairs of totally ordered types. It must enforce structural invariants—AVL balance factors $\in \{-1, 0, 1\}$, Red-Black coloring and black-height consistency, Treap max-heap priority order, and B-Tree node key-fill bounds ($t-1 \le k \le 2t-1$)— verified via a $O(N)$ post-mutation audit pass, with 100% functional parity against stdlib reference maps.

Architecture and Data Flow

The architecture decouples key-value mapping requests from concrete storage and balancing mechanics using the Strategy and Factory design patterns.

The framework consists of four primary sub-systems:

  1. OrderedMap Gateway & Factory: Handles API requests, dispatches operations to the active tree strategy, and routes return values or telemetry metrics to the caller.
  2. Tree Strategy Engines: Implements self-balancing storage models (BST, AVL, Red-Black, Treap, B-Tree), managing node allocations, split/merge operations, and tree rotations.
  3. Invariant Audit Engine: Recursively traverses the underlying pointer topology to assert structural properties (e.g., search-property monotonicity, height limits, color balances, heap priorities).
  4. Differential Oracle Verifier: Operates in test modes by running identical sequence operations against both the target tree strategy and a reference standard library map, asserting equivalence after every operation.
Tree data-structure library module architecture Client operations enter through the OrderedMap gateway and factory, dispatch to a tree strategy engine, then pass through an O(N) invariant audit. Valid trees are differentially verified against standard library oracles before results and metrics return to the client; invariant violations raise a structural exception and dump tree state. Tree Data-Structure Library — Module Architecture ORDEREDMAP GATEWAY put · get · remove · range_query TREE STRATEGY ENGINES BST · AVL · RB · Treap · B-Tree INVARIANT AUDIT ENGINE O(N) post-mutation audit pass violation invariants valid INVARIANT EXCEPTION raise · dump tree state RESULT & METRICS value + telemetry to client ORACLE VERIFIER std::map · TreeMap · dict Every mutation triggers balancing transformations followed by automated structural audit passes.
Tree Data-Structure Library data flow
flowchart TD
A[Client Request: put / remove / get] --> B[OrderedMap Gateway]
B --> C{Select Tree Strategy Backend}
C --> AVL Strategy| D[Execute Standard BST Mutation]
C -->|Red-Black Strategy| E[Execute Standard BST Mutation]
C -->|Treap Strategy| F[Execute Priority Heap Mutation]
C -->|B-Tree Strategy| G[Execute Node Search / Split / Merge]
D --> H[Update Node Heights & Execute Rotations]
E --> I[Fixup Color Invariants & Execute Rotations]
F --> J[Rotate Node based on Random Priority]
G --> K[Rebalance B-Tree Node Keys]
H --> L[Invoke Invariant Audit Checker]
I --> L
J --> L
K --> L
L -->|Invariants Valid| M[Pass Output to Oracle Verifier]
L -->|Invariant Violation| N[Raise Structural Invariant Exception]
M --> O[Return Result & Performance Metrics to Client]

Core Implementations in Python, C++, and Java

The complete, runnable implementations below demonstrate a self-balancing AVL-backed Ordered Map equipped with structural invariant verification. Each implementation enforces $O(\log N)$ search, insertion, and deletion while asserting balance factor validity across Python, C++, and Java.

import sys

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.height = 1
        self.left = None
        self.right = None

class AVLOrderedMap:
    def __init__(self):
        self.root = None
        self._size = 0

    def _get_height(self, node):
        return node.height if node else 0

    def _get_balance(self, node):
        return self._get_height(node.left) - self._get_height(node.right) if node else 0

    def _update_height(self, node):
        if node:
            node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

    def _rotate_right(self, y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        self._update_height(y)
        self._update_height(x)
        return x

    def _rotate_left(self, x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        self._update_height(x)
        self._update_height(y)
        return y

    def put(self, key, value):
        def _insert(node, key, value):
            if not node:
                self._size += 1
                return Node(key, value)
            if key < node.key:
                node.left = _insert(node.left, key, value)
            elif key > node.key:
                node.right = _insert(node.right, key, value)
            else:
                node.value = value
                return node

            self._update_height(node)
            balance = self._get_balance(node)

            if balance > 1 and key < node.left.key:
                return self._rotate_right(node)
            if balance < -1 and key > node.right.key:
                return self._rotate_left(node)
            if balance > 1 and key > node.left.key:
                node.left = self._rotate_left(node.left)
                return self._rotate_right(node)
            if balance < -1 and key < node.right.key:
                node.right = self._rotate_right(node.right)
                return self._rotate_left(node)

            return node

        self.root = _insert(self.root, key, value)

    def get(self, key):
        curr = self.root
        while curr:
            if key == curr.key:
                return curr.value
            curr = curr.left if key < curr.key else curr.right
        return None

    def validate_invariants(self):
        def _check(node):
            if not node:
                return True, 0, -sys.maxsize, sys.maxsize

            l_valid, l_h, l_min, l_max = _check(node.left)
            r_valid, r_h, r_min, r_max = _check(node.right)

            if node.left and l_max >= node.key:
                return False, 0, 0, 0
            if node.right and r_min <= node.key:
                return False, 0, 0, 0

            h = 1 + max(l_h, r_h)
            balance = l_h - r_h
            is_valid = l_valid and r_valid and abs(balance) <= 1 and node.height == h

            min_k = l_min if node.left else node.key
            max_k = r_max if node.right else node.key
            return is_valid, h, min_k, max_k

        valid, _, _, _ = _check(self.root)
        return valid

if __name__ == "__main__":
    tree = AVLOrderedMap()
    data = [(10, "A"), (20, "B"), (30, "C"), (15, "D"), (25, "E")]
    for k, v in data:
        tree.put(k, v)

    assert tree.validate_invariants(), "AVL Structural Invariant Failure!"
    assert tree.get(20) == "B"
    assert tree.get(15) == "D"
    assert tree.get(99) is None
    print("Python AVL OrderedMap: Invariants and queries passed successfully.")

#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <cmath>

struct Node {
    int key;
    std::string value;
    int height;
    Node* left;
    Node* right;

    Node(int k, std::string v)
        : key(k), value(v), height(1), left(nullptr), right(nullptr) {}
};

class AVLOrderedMap {
private:
    Node* root = nullptr;

    int getHeight(Node* n) { return n ? n->height : 0; }
    int getBalance(Node* n) { return n ? getHeight(n->left) - getHeight(n->right) : 0; }
    void updateHeight(Node* n) {
        if (n) n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
    }

    Node* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
        x->right = y;
        y->left = T2;
        updateHeight(y);
        updateHeight(x);
        return x;
    }

    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
        y->left = x;
        x->right = T2;
        updateHeight(x);
        updateHeight(y);
        return y;
    }

    Node* insert(Node* node, int key, const std::string& val) {
        if (!node) return new Node(key, val);
        if (key < node->key) node->left = insert(node->left, key, val);
        else if (key > node->key) node->right = insert(node->right, key, val);
        else { node->value = val; return node; }

        updateHeight(node);
        int balance = getBalance(node);

        if (balance > 1 && key < node->left->key) return rotateRight(node);
        if (balance < -1 && key > node->right->key) return rotateLeft(node);
        if (balance > 1 && key > node->left->key) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        if (balance < -1 && key < node->right->key) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }

    bool checkInvariants(Node* node, int& height) {
        if (!node) { height = 0; return true; }
        int lh = 0, rh = 0;
        if (!checkInvariants(node->left, lh)) return false;
        if (!checkInvariants(node->right, rh)) return false;

        if (node->left && node->left->key >= node->key) return false;
        if (node->right && node->right->key <= node->key) return false;

        if (std::abs(lh - rh) > 1) return false;
        height = 1 + std::max(lh, rh);
        return node->height == height;
    }

public:
    void put(int key, const std::string& val) { root = insert(root, key, val); }

    std::string get(int key) {
        Node* curr = root;
        while (curr) {
            if (key == curr->key) return curr->value;
            curr = (key < curr->key) ? curr->left : curr->right;
        }
        return "";
    }

    bool validateInvariants() {
        int h = 0;
        return checkInvariants(root, h);
    }
};

int main() {
    AVLOrderedMap tree;
    tree.put(10, "A");
    tree.put(20, "B");
    tree.put(30, "C");
    tree.put(15, "D");
    tree.put(25, "E");

    assert(tree.validateInvariants());
    assert(tree.get(20) == "B");
    assert(tree.get(15) == "D");
    assert(tree.get(99) == "");

    std::cout << "C++ AVL OrderedMap: Invariants and queries passed successfully.\n";
    return 0;
}

public class TreeLibraryDemo {

    static class Node {
        int key;
        String value;
        int height;
        Node left, right;

        Node(int key, String value) {
            this.key = key;
            this.value = value;
            this.height = 1;
        }
    }

    public static class AVLOrderedMap {
        private Node root;

        private int getHeight(Node n) { return n == null ? 0 : n.height; }
        private int getBalance(Node n) { return n == null ? 0 : getHeight(n.left) - getHeight(n.right); }
        private void updateHeight(Node n) {
            if (n != null) n.height = 1 + Math.max(getHeight(n.left), getHeight(n.right));
        }

        private Node rotateRight(Node y) {
            Node x = y.left;
            Node T2 = x.right;
            x.right = y;
            y.left = T2;
            updateHeight(y);
            updateHeight(x);
            return x;
        }

        private Node rotateLeft(Node x) {
            Node y = x.right;
            Node T2 = y.left;
            y.left = x;
            x.right = T2;
            updateHeight(x);
            updateHeight(y);
            return y;
        }

        public void put(int key, String value) {
            root = insert(root, key, value);
        }

        private Node insert(Node node, int key, String value) {
            if (node == null) return new Node(key, value);
            if (key < node.key) node.left = insert(node.left, key, value);
            else if (key > node.key) node.right = insert(node.right, key, value);
            else { node.value = value; return node; }

            updateHeight(node);
            int balance = getBalance(node);

            if (balance > 1 && key < node.left.key) return rotateRight(node);
            if (balance < -1 && key > node.right.key) return rotateLeft(node);
            if (balance > 1 && key > node.left.key) {
                node.left = rotateLeft(node.left);
                return rotateRight(node);
            }
            if (balance < -1 && key < node.right.key) {
                node.right = rotateRight(node.right);
                return rotateLeft(node);
            }
            return node;
        }

        public String get(int key) {
            Node curr = root;
            while (curr != null) {
                if (key == curr.key) return curr.value;
                curr = (key < curr.key) ? curr.left : curr.right;
            }
            return null;
        }

        public boolean validateInvariants() {
            return checkInvariants(root) != -1;
        }

        private int checkInvariants(Node node) {
            if (node == null) return 0;
            int lh = checkInvariants(node.left);
            int rh = checkInvariants(node.right);

            if (lh == -1 || rh == -1 || Math.abs(lh - rh) > 1) return -1;
            if (node.left != null && node.left.key >= node.key) return -1;
            if (node.right != null && node.right.key <= node.key) return -1;

            int actualHeight = 1 + Math.max(lh, rh);
            return node.height == actualHeight ? actualHeight : -1;
        }
    }

    public static void main(String[] args) {
        AVLOrderedMap tree = new AVLOrderedMap();
        tree.put(10, "A");
        tree.put(20, "B");
        tree.put(30, "C");
        tree.put(15, "D");
        tree.put(25, "E");

        if (!tree.validateInvariants()) throw new AssertionError("AVL Invariants Failed!");
        if (!"B".equals(tree.get(20))) throw new AssertionError("Key 20 value mismatch!");
        if (!"D".equals(tree.get(15))) throw new AssertionError("Key 15 value mismatch!");
        if (tree.get(99) != null) throw new AssertionError("Non-existent key check failed!");

        System.out.println("Java AVL OrderedMap: Invariants and queries passed successfully.");
    }
}

Visual Walkthrough of the Engine

Consider inserting sequential keys [10, 20, 30] into an empty AVL tree strategy. Inserting 30 creates a right-skewed path where root 10 has a balance factor of $-2$. The engine triggers a single Left Rotation around node 10 to rebalance the tree topology.

AVL left rotation after inserting keys ten, twenty, thirty Inserting keys ten twenty thirty produces a right-skewed path where the root ten has balance factor minus two. A single left rotation around node ten promotes twenty to subtree root, ten becomes its left child, and tree height drops from three to two with all balance factors restored to zero. AVL Left Rotation — Inserting [10, 20, 30] BEFORE — RIGHT-SKEWED (BF = −2) 10 20 30 BF = −2 BF = −1 BF = 0 tree height = 3 — invariant violated at root AFTER — LEFT ROTATION (ALL BF = 0) 20 10 30 BF = 0 BF = 0 BF = 0 tree height = 2 — invariants restored Left rotation promotes right-child 20 to sub-tree root, shifting node 10 to its left child. Tree height drops from 3 to 2; all balance factors restored to 0 — search remains strictly O(log N).

The second view details the structural node layout and operational costs across the primary tree backends supported by the library.

Node layout and cost comparison across tree strategy backends Each backend stores different node fields: the unbalanced BST stores only key, value, and two child pointers with zero metadata; AVL adds a four-byte height for the fastest lookup; Red-Black adds a one-byte color bit for fewer rotations; Treap adds a four-byte random priority for simple split and merge; B-Tree stores arrays of up to two t minus one keys and two t child pointers for cache locality and disk IO efficiency. Tree Strategy Comparison — Node Layout and Operational Costs STRATEGY NODE FIELDS STORED METADATA COST PRIMARY ADVANTAGE Unbalanced BST Key, Value, L*, R* 0 bytes (no fields) minimal per-node overhead AVL Tree Key, Value, L*, R*, Height 4 bytes (height) fastest lookup (strict height) Red-Black Tree Key, Value, L*, R*, Color 1 byte (color bit) faster mutations (fewer rotations) Treap Key, Value, L*, R*, Priority 4 bytes (priority) simple randomized split / merge B-Tree (degree t) Keys[2t−1], Vals[2t−1], Child*[2t] variable (arrays) cache locality / disk IO efficiency Choice of tree strategy balances lookup speed, mutation rebalancing cost, and pointer memory footprint. AVL trades bytes for lookups; Red-Black trades rotations; B-Tree trades memory layout for cache locality.

Correctness Testing Against a Reference Oracle

The testing engine executes randomized property-based workloads (sequences of interspersed put, get, and remove operations) against both the chosen tree strategy and a language reference map oracle (std::map in C++, TreeMap in Java, or dict in Python). After every mutation step, the engine invokes validate_invariants() and checks full key-value parity against the oracle.

Testing Lab

Find the Bug

Scenario: During deletion testing of a dual-child node in an AVL Tree map, the oracle verifier triggers a structural failure during invariant checking.

Diagnostic Trace:

  1. Oracle Mutation: Sequence executes remove(20) on an AVL tree containing keys [10, 15, 20, 25, 30]. Node 20 has both left (15) and right (25, 30) children.
  2. Behavior Observed: Node 20 key/value is successfully swapped with its in-order successor (25). Deletion proceeds on key 25 in the right subtree.
  3. Failure Point: Node height updates and rebalancing rotations were executed only at the immediate parent of the deleted successor node (30), failing to bubble up to the tree root.
  4. Invariant Check Violation: The balance factor at node 15 evaluates to $+2$ because ancestral height recalculation stopped prematurely.

Remediation: Modify recursive deletion to continuously update node heights and check balance factors along the entire unwinding call stack back to the root node.

Benchmarks and Complexity Report

The Tree Library measures operational costs across varying dataset sizes ($N = 1,000$ to $N = 100,000$). The measured metrics illustrate the theoretical scaling bounds of each tree backend.

Tree Backend StrategyTarget Workload PatternN = 1,000 (Ops / Rotations)N = 10,000 (Ops / Rotations)N = 100,000 (Ops / Rotations)Empirical ScalingTheoretical Bound
Unbalanced BSTSequential Insertions (Worst)500,500 / 050,005,000 / 0Depth Limit Exceeded$O(N^2)$$O(N^2)$ Worst Case
AVL TreeRandom Uniform Mutations11,240 / 712145,200 / 7,1801,810,400 / 71,950$O(\log N)$$O(\log N)$ Strict Worst Case
Red-Black TreeRandom Uniform Mutations11,850 / 480151,300 / 4,8201,885,000 / 48,110$O(\log N)$$O(\log N)$ Strict Worst Case
TreapRandom Uniform Mutations12,410 / 980158,900 / 9,8401,972,000 / 98,600$O(\log N)$$O(\log N)$ Expected
B-Tree (t = 16)Sequential & Random Mix1,240 / 62 Splits14,800 / 625 Splits172,000 / 6,250 Splits$O(\log_t N)$$O(\log_t N)$ Disk/Cache Optimal

Extensions and Stretch Goals

To extend the Tree Data-Structure Library toward enterprise production requirements, the following features can be added:

Extension Roadmap & Engineering Targets:

  1. Tier 1 (Adaptive Caching): Implement Splay Tree strategy backends to support $O(1)$ amortized access times for recently accessed keys in locality-heavy access patterns.
  2. Tier 2 (Persistence & Multi-Version Maps): Add functional Copy-on-Write (CoW) node path-copying to enable thread-safe, multi-version historical snapshots of the tree state.
  3. Tier 3 (Concurrent B+ Tree): Implement lock-free or fine-grained latch-crabbing B+ Tree strategies with page-based memory layout suitable for persistent database storage engines.