AVL, RB, LLRB tree's, and a OpenGL based Tree visualizer.

tree-viz.cpp

#include <vector>
#include <limits>
#include <iostream>
#include <SFML/Graphics.hpp>
using namespace std;

template <class K, class V>
struct rbnode {
    K key;
    V value;
    int height;
    bool color;
    rbnode* left;
    rbnode* right;
    rbnode(K k, V v, bool c, rbnode* l, rbnode* r) {
        key = k; value = v; color = c; left = l; right = r; height = 0;
    }
    rbnode(K key_, V value_) {
        key = key_; value = value_;
        color = true;
        left = nullptr; right = nullptr;
        height = 0;
    }
};

template <class K, class V>
class TreeDraw {
    private:
        bool isRedBlack;
        using nodeptr = rbnode<K,V>*;
        int X;
        int Y;
        nodeptr nilmarker;
        nodeptr head;
        vector<sf::CircleShape> nodes;
        void mark(nodeptr h) {
            Y++;
            if (h != nilmarker) {
                mark(h->left);
                sf::CircleShape tmp(13);
                tmp.setPosition(((++X)*22), (Y*2)*22);
                if (h == head) {
                    tmp.setOutlineColor(sf::Color::Blue);
                    tmp.setOutlineThickness(5);
                }
                if (isRedBlack) {
                    if (h->color) tmp.setFillColor(sf::Color(255,0,0));
                    else tmp.setFillColor(sf::Color::Black);
                } else {
                    tmp.setFillColor(sf::Color::Blue);
                }
                nodes.push_back(tmp);
                mark(h->right);
            }
            Y--;
        }
    public:
        TreeDraw() {
            
        }
        void mark(rbnode<K,V>* root, rbnode<K,V>* nil, bool redblack) {
            isRedBlack = redblack;
            nilmarker = nil;
            head = root;
            X += 2;
            mark(root);
        }
        void drawTree() {
            sf::RenderWindow window(sf::VideoMode(2000,480), "Self-Balanacing Binary Search Trees");
            while (window.isOpen()) {
                sf::Event event;
                while (window.pollEvent(event)) {
                    if (event.type == sf::Event::Closed)
                        window.close();
                }
                window.clear(sf::Color::White);
                for (auto node : nodes) {
                    window.draw(node);
                }
                window.display();
            }
        }
};

template <class K, class V>
class AVL {
    private:
        using Node = rbnode<K,V>*;
        Node root;
        int count;
        int height(Node h) {
            return (h == nullptr) ? -1:h->height;
        }
        Node adjustheight(Node h) {
            h->height = 1+max(height(h->left), height(h->right));
            return h;
        }
        Node rotL(Node h) {
            Node x = h->right;
            h->right = x->left;
            x->left = h;
            h = adjustheight(h);
            x = adjustheight(x);
            lrcount++;
            return x;
        }
        Node rotR(Node h) {
            Node x = h->left; h->left = x->right;
            x->right = h;
            h = adjustheight(h);
            x = adjustheight(x);
            rrcount++;
            return x;
        }
        int balanceFactor(Node h) {
            return height(h->left) - height(h->right);
        }
        Node balance(Node h) {
            if (balanceFactor(h) < -1) {
                if (balanceFactor(h->right) > 0)
                    h->right = rotR(h->right);
                h = rotL(h);
            } else if (balanceFactor(h) > 1) {
                if (balanceFactor(h->left) < 0)
                    h->left = rotL(h->left);
                h = rotR(h);
            }
            return h;
        }
        Node insert(Node h, K key, V value) {
            if (h == nullptr) {
                return new rbnode<K,V>(key, value);
            }
            if (key < h->key) h->left = insert(h->left, key, value);
            else h->right = insert(h->right, key, value);
            h = adjustheight(h);
            return balance(h);
        }
        void inorder(Node h) {
            if (h == nullptr) return;
            inorder(h->left);
            cout<<h->key<<" ";
            inorder(h->right);
        }
        void visit(Node h) {
            if (h != nullptr) {
                cout<<h->key<<" ";
                visit(h->left);
                visit(h->right);
            }
        }
        int lrcount;
        int rrcount;
        void cleanup(Node h) {
            if (h != nullptr) {
                cleanup(h->left);
                cleanup(h->right);
                delete h;
            }
        }
    public:
        AVL() {
            root = nullptr;
            count = 0;
            lrcount = 0;
            rrcount = 0;
        }
        ~AVL() {
            cleanup(root);
        }
        void insert(K key, V value) {
            root = insert(root, key, value);
            count++;
        }
        void show() {
            cout<<"Left rotations:  "<<lrcount<<endl;
            cout<<"Right rotations: "<<rrcount<<endl;
            cout<<"Nodes: "<<count<<endl;
            cout<<"Height: "<<1+height(root)<<endl;
        }
        int height() {
            return 1+height(root);
        }
        void sort(){
            inorder(root);
            cout<<endl;
        }
        Node rootNode() {
            return root;
        }
        Node nil() {
            return nullptr;
        }
};


const bool black = false;
const bool red = true;


template <class K, class V>
class RedBlack {
    public:
        using nodeptr = rbnode<K,V>*;
    private:
        int lrcount;
        int rrcount;
        int splitcount;
        nodeptr head, z;
        nodeptr x, p, g, gg;
        nodeptr rotate(K key, nodeptr y) {
            nodeptr c, gc;
            c = (key < y->key) ? y->left:y->right;
            if (key < c->key) {
                rrcount++;
                gc = c->left; c->left = gc->right; gc->right = c;
            } else {
                lrcount++;
                gc = c->right; c->right = gc->left; gc->left = c;
            }
            if (key < y->key) y->left = gc; else y->right = gc;
            return gc;
        }
        void split(K key) {
            splitcount++;
            x->color = red; x->left->color = black; x->right->color = black;
            if (p->color) {
                g->color = red;
                if (key < p->key != key < g->key) p = rotate(key, g);
                x = rotate(key, gg);
                x->color = black;
            }
        }
        int height(nodeptr h) {
            if (h == z)
                return -1;
            return 1 + max(height(h->left), height(h->right));
        }
        int n;
        void cleanup(nodeptr h) {
            if (h != z) {
                cleanup(h->left);
                cleanup(h->right);
                delete h;
            }
        }
    public:
        RedBlack() {
            z = new rbnode<K,V>(std::numeric_limits<K>::max(), std::numeric_limits<V>::max(), false, nullptr, nullptr);
            z->right = z; z->left = z;
            head = new rbnode<K,V>(std::numeric_limits<K>::min(), std::numeric_limits<V>::min(), false,z,z);
            n = 0; lrcount = 0; rrcount = 0; splitcount = 0;
        }
        ~RedBlack() {
            cleanup(head->right);
            delete head;
            delete z;
        }
        void insert(K key, V value) {
            x = head; p = x; g = x;
            while (x != z) {
                gg = g; g = p; p = x;
                x = (key < x->key) ? x->left:x->right;
                if (x->left->color && x->right->color)
                    split(key);
            }
            x = new rbnode<K,V>(key, value, true, z, z);
            if (key < p->key) p->left = x; else p->right = x;
            split(key);
            head->right->color = false;
            n++;
        }
        int size() {
            return n;
        }
        int height() {
            return 1+height(head->right);
        }
        nodeptr rootNode() {
            return head->right;
        }
        nodeptr nil() {
            return z;
        }
};

template <class K, class V>
class LeftLeaningRedBlack {
    private:
        using nodeptr = rbnode<K,V>*;
        nodeptr root;
        int count;
        int lrcount;
        int rrcount;
        int splitcount;
        bool isRed(nodeptr h) {
            return (h == nullptr) ? false:(h->color == true);
        }
        nodeptr rotL(nodeptr h) {
            lrcount++;
            nodeptr x = h->right;
            h->right = x->left;
            x->left = h;
            x->color = h->color;
            h->color = true;
            return x;
        }
        nodeptr rotR(nodeptr h) {
            rrcount++;
            nodeptr x = h->left;
            h->left = x->right;
            x->right = h;
            x->color = h->color;
            h->color = true;
            return x;
        }
        nodeptr flipColor(nodeptr h) {
            splitcount++;
            h->color = !h->color;
            h->left->color = !h->left->color;
            h->right->color = !h->right->color;
            return h;
        }
        nodeptr balance(nodeptr h) {
            if (isRed(h->right) && !isRed(h->left)) h = rotL(h);
            if (isRed(h->left) && isRed(h->left->left)) h = rotR(h);
            if (isRed(h->right) && isRed(h->left)) h = flipColor(h);
            return h;
        }
        nodeptr insert(nodeptr h, K key, V value) {
            if (h == nullptr)
                return new rbnode(key, value);
            if (key < h->key) h->left = insert(h->left, key, value);
            else h->right = insert(h->right, key, value);
            return balance(h);
        }
        void buildStats() {
            cout<<"Left rotations:  "<<lrcount<<endl;
            cout<<"Right rotations: "<<rrcount<<endl;
            cout<<"Color splits:    "<<splitcount<<endl;
            cout<<"Nodes: "<<size()<<endl;
            cout<<"Height: "<<height()<<endl;
        }
        int height(nodeptr h) {
            if (h == nullptr)
                return -1;
            return 1 + max(height(h->left), height(h->right));
        }
        void cleanup(nodeptr h) {
            if (h != nullptr) {
                cleanup(h->left);
                cleanup(h->right);
                delete h;
            }
        }
    public:
        LeftLeaningRedBlack() {
            root = nullptr;
            count = 0;
            lrcount = 0;
            rrcount = 0;
            splitcount = 0;
        }
        ~LeftLeaningRedBlack() {
            cleanup(root);
        }
        bool empty() {
            return root == nullptr;
        }
        int size() {
            return count;
        }
        void insert(K key, V value) {
            root = insert(root, key, value);
            count++;
        }
        void show() {
            buildStats();
        }
        nodeptr rootNode() {
            return root;
        }
        nodeptr nil() {
            return nullptr;
        }
        int height() {
            return 1+height(root);
        }
};