A B Tree of Binary Search Trees

mgcadmin 02-18-2026

Ever seen a B Tree made of Binary Search Trees before?

template <class T, int M>
class BTree {
    private:
        using Node = Page<T,M>;
        using link = Node*;
        int n;
        link root;
        void __primeStack(stack<node<T,M>*>& sf, node<T,M>* m) {
            while (m != nullptr) {
                sf.push(m);
                m = m->left;
            }
        }
        void __processPage(link curr, queue<link>& fq) {
            if (curr != nullptr) {
                cout<<"[ ";
                stack<node<T,M>*> sf;
                __primeStack(sf, curr->root);
                while (!sf.empty()) {
                    m = sf.top(); sf.pop();
                    if (m != nullptr) {
                        cout<<m->key<<" ";
                        fq.push(m->child);
                        __primeStack(m->right);
                    }
                }
                cout<<"] ";
            }
        }
        void add(link curr, T key) {
            if (curr->isExternal()) {
                curr->add(key);
                n++;
            } else {
                link next = curr->next(key);
                add(next, key);
                if (next->full()) {
                    curr->add(next->split());
                }
            }
        }
        bool contains(link curr, T key) {
            if (curr->isExternal()) {
                return curr->contains(key);
            }
            return contains(curr->next(key), key);
        }
        link popQueue(queue<link>& fq) {
            auto curr = fq.front(); fq.pop();
            return curr;
        }
    public:
        BTree() {
            root = new Node();
            n = 0;
        }
        void add(T key) {
            add(root, key);
            if (root->full()) {
                link lhs = root;
                link rhs = root->split();
                root = new Node();
                root->add(lhs);
                root->add(rhs);
            }
        }
        bool contains(T key) {
            return contains(root, key);
        }
        //performs level order traversal of tree
        // by performin in-order traversal of each page
        void print() {
            queue<link> fq;
            fq.push(root);
            while (!fq.empty()) {
                int nc = fq.size();
                while (nc > 0) {
                    auto curr = __popQueue(fq); nc--;
                    __processPage(curr, fq);
                }
                cout<<endl;
            }
        }
};

Now you have.

template <class T, int M>
class Page;

template <class T, int M>
struct node {
    T key;
    Page<T,M>* child;
    int size;
    node* left;
    node* right;
    node(T k, Page<T,M>* page) : key(k), size(1), child(page), left(nullptr), right(nullptr) { }
    node(T k = T()) : key(k), size(1), child(nullptr), left(nullptr), right(nullptr) { }
};

template <class T, int M>
int size(node<T,M>* h) {
    return h == nullptr ? 0:h->size;
}

template <class T, int M>
node<T,M>* rotL(node<T,M>* h) {
    auto x = h->right; h->right = x->left; x->left = h;
    h->size = 1 + size(h->left) + size(h->right);
    x->size = 1 + size(x->left) + size(x->right);
    return x;
}

template <class T, int M>
node<T,M>* rotR(node<T,M>* h) {
    auto x = h->left; h->left = x->right; x->right = h;
    h->size = 1 + size(h->left) + size(h->right);
    x->size = 1 + size(x->left) + size(x->right);
    return x;
}

template <class T, int M>
node<T,M>* partR(node<T,M>* h, int r) {
    if (h == nullptr)
        return nullptr;
    int t = (h->left == nullptr) ? 0:h->left->size;
    if (t > r) {
        h->left = partR(h->left, r);
        h = rotR(h);
    }
    if (t < r) {
        h->right = partR(h->right, r - t - 1);
        h = rotL(h);
    }
    return h;
}

template <class T, int M>
node<T,M>* joinLR(node<T,M>* a, node<T,M>* b) {
    if (b == nullptr) return a;
    b = partR(b, 0); b->left = a;
    b->size = 1 + size(b->right) + size(a);
    return b;
}

template <class T, int M>
node<T,M>* putR(node<T,M>* h, T key, Page<T,M>* p) {
    if (h == nullptr)
        return new node<T,M>(key, p);
    if (key == h->key && p != nullptr) {
        h->left = putR(h->left, key, p);
        h = rotR(h);
    } else if (key < h->key) {
        h->left = putR<T,M>(h->left, key, p);
        h = rotR(h);
    } else {
        h->right = putR<T,M>(h->right, key, p);
        h = rotL(h);
    }
    h->size = 1 + size(h->left) + size(h->right);
    return h = partR(h, h->size/2 -1);
}

template <class T, int M>
class BTree;

template <class T, int M = 5>
class Page {
    private:
        friend class BTree<T,M>;
        using bnode = node<T,M>;
        using link = bnode*;
        int n;
        int maxN;
        link root;
        bool isLeaf(link h) {
            if (h == nullptr)
                return false;
            return h->left == nullptr && h->right == nullptr;
        }
        link floor(link h, T key) {
            if (h == nullptr)
                return h;
            if (key == h->key)
                return h;
            if (key < h->key)
                return floor(h->left, key);
            link t = floor(h->right, key);
            if (t != nullptr)
                return t;
            return h;
        }
    public:
        Page(int maxsize = M) {
            n = 0;
            maxN = maxsize;
        }
        Page(link head, int N) {
            root = head;
            n = N;
            maxN = M;
        }
        bool empty() const {
            return n == 0;
        }
        bool full() const {
            return n == maxN;
        }
        bool isExternal() {
            if (root == nullptr)
                return true;
            return root->child == nullptr;
        }
        T min() {
            link x = root;
            while (x != nullptr) {
                if (x->left == nullptr)
                    break;
                x = x->left;
            }
            return x->key;
        }
        bool contains(T key) {
            link x = root;
            while (x != nullptr) {
                if (x->key == key)
                    return true;
                x = key < x->key ? x->left:x->right;
            }
            return false;
        }
        void add(T key) {
            root = putR(root, key, (Page<T,M>*)nullptr);
            n++;
        }
        void add(Page<T,M>* page) {
            root = putR(root, page->min(), page);
            n++;
        }
        Page<T,M>* split() {
            cout<<"Splitting: ";
            print();
            root = partR(root, root->size/2-1);
            n -= root->right->size;
            link t = root->right;
            root->right = nullptr;
            Page<T,M>* np = new Page<T,M>(t, t->size);
            cout<<"Old Page: ";
            print();
            cout<<"New Page: ";
            np->print();
            return np;
        }
        Page<T,M>* next(T key) {
            if (root == nullptr)
                return this;
            link t = floor(root, key);
            if (t != nullptr) {
                return t->child;
            }
            return this;
        }
        void print() {
            iterativeInorder(root);
        }
};

---