Created
October 25, 2023 18:50
-
-
Save maxgoren/9d86c17e4ef6fab602e2b297983d3a5f to your computer and use it in GitHub Desktop.
AVL, RB, LLRB tree's, and a OpenGL based Tree visualizer.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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