Skip to content

Instantly share code, notes, and snippets.

@maxgoren
Created October 25, 2023 18:50
Show Gist options
  • Save maxgoren/9d86c17e4ef6fab602e2b297983d3a5f to your computer and use it in GitHub Desktop.
Save maxgoren/9d86c17e4ef6fab602e2b297983d3a5f to your computer and use it in GitHub Desktop.
AVL, RB, LLRB tree's, and a OpenGL based Tree visualizer.
#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);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment