
ST Using Left-Leaning Red-Black Tree
Maps are implemented using Red-Black Trees
#include <iostream>
#include <queue>
using namespace std;
const bool RED = true;
const bool BLACK = false;
template <typename Key, typename Value>
struct Node
{
Node *left, *right;
Key key;
Value val;
bool color; // color of child to parent link
public:
Node(Key key, Value val, bool color)
{
left = right = nullptr;
this->color = color;
this->key = key;
this->val = val;
}
};
template <typename Key, typename Value>
class RedBlackTree
{
Node<Key, Value> *root;
// Main Operations
bool isRed(Node<Key, Value> *x)
{
return (x == nullptr) ? false : x->color == RED; // null and right side links are always black
}
// Orient a (temporarily) right-leaning red link to lean left.
Node<Key, Value> *rotateLeft(Node<Key, Value> *h)
{
Node<Key, Value> *x = h->right;
h->right = x->left;
x->left = h;
x->color = h->color;
h->color = RED;
return x;
}
// Orient a left-leaning red link to (temporarily) lean right.
Node<Key, Value> *rotateRight(Node<Key, Value> *h)
{
Node<Key, Value> *x = h->left;
h->left = x->right;
x->right = h;
x->color = h->color;
h->color = RED;
return x;
}
// Recolor to split a (temporary) 4-node.
void flipColor(Node<Key, Value> *h)
{
h->color = RED;
h->left->color = BLACK;
h->right->color = BLACK;
}
Node<Key, Value> *put(Node<Key, Value> *h, Key key, Value val)
{
if (h == nullptr)
return new Node<Key, Value>(key, val, RED);
if (h->key > key)
h->left = put(h->left, key, val);
else if (h->key < key)
h->right = put(h->right, key, val);
else
h->val = val;
if (isRed(h->right) && !isRed(h->left))
h = rotateLeft(h);
if (isRed(h->left) && isRed(h->left->left))
h = rotateRight(h);
if (isRed(h->left) && isRed(h->right))
flipColor(h);
return h;
}
Node<Key, Value> *floor(Node<Key, Value> *x, Key key)
{
if (x == nullptr)
return nullptr;
if (key == x->key)
return x;
if (key < x->key)
return floor(x->left, key);
Node<Key, Value> *temp = floor(x->right, key);
if (temp != nullptr)
return temp;
else
return x;
}
void levelorder(Node<Key, Value> *x)
{
queue<Node<Key, Value> *> qt;
qt.push(root);
qt.push(nullptr);
cout << x->key << ": " << x->val << " " << endl;
while (!qt.empty())
{
Node<Key, Value> *cur = qt.front();
qt.pop();
if (cur != nullptr)
{
if (cur->left != nullptr)
{
qt.push(cur->left);
cout << cur->left->key << ": " << cur->left->val << " ";
}
if (cur->right != nullptr)
{
qt.push(cur->right);
cout << cur->right->key << ": " << cur->right->val << " ";
}
}
if (qt.front() == nullptr)
{
cout << endl;
qt.pop();
qt.push(nullptr);
}
}
}
Node<Key, Value> *delMax(Node<Key, Value> *x)
{
if (x->right == nullptr)
{
Node<Key, Value> *temp = x->left;
return temp;
}
x->right = delMax(x->right);
return x;
}
Node<Key, Value> *delMin(Node<Key, Value> *x)
{
if (x->left == nullptr)
{
// Node<Key, Value> *temp = x;
return x->right;
}
x->left = delMin(x->left);
return x;
}
Node<Key, Value> *min(Node<Key, Value> *x)
{
Node<Key, Value> *temp = x;
while (temp->left != nullptr)
{
temp = temp->left;
}
return temp;
}
Node<Key, Value> *max(Node<Key, Value> *x)
{
Node<Key, Value> *temp = x;
while (temp->right != nullptr)
{
temp = temp->right;
}
return temp;
}
// Hibbard deletion: Simple BST Deletion
Node<Key, Value> *delPair(Node<Key, Value> *x, Key key)
{
if (x == nullptr)
return x;
if (key < x->key)
x->left = delPair(x->left, key);
else if (key > x->key)
x->right = delPair(x->right, key);
else
{
if (x->left == nullptr)
return x->right;
if (x->right == nullptr)
return x->left;
Node<Key, Value> *t = x;
x = min(t->right);
x->right = delMin(t->right); // will return t->right
x->left = t->left;
}
return x;
}
public:
void put(Key key, Value val)
{
root = put(root, key, val);
}
Key floor(Key key)
{
Node<Key, Value> *x = floor(root, key);
if (x == nullptr)
throw "";
return x->key;
}
Value get(Key key)
{
Node<Key, Value> *cur = root;
while (cur != nullptr)
{
if (cur->key < key)
{
cur = cur->right;
}
else if (cur->key > key)
cur = cur->left;
else
return cur->val;
}
throw "Key Not found!";
}
void print_levelorder()
{
levelorder(root);
}
Key min()
{
if (root == nullptr)
throw "Empty Symbol Table";
Node<Key, Value> *temp = min(root);
return temp->key;
}
Key max()
{
if (root == nullptr)
throw "Empty Symbol Table";
Node<Key, Value> *temp = max(root);
return temp->key;
}
void delMin()
{
root = delMin(root);
}
void delMax()
{
root = delMax(root);
}
void delPair(Key key)
{
root = delPair(root, key);
}
};
int main()
{
RedBlackTree<char, int> *rb = new RedBlackTree<char, int>();
rb->put('S', 1);
rb->put('E', 2);
rb->put('A', 3);
rb->put('R', 4);
rb->put('C', 5);
rb->put('H', 6);
rb->put('X', 7);
rb->put('M', 8);
rb->put('P', 9);
rb->put('L', 10);
rb->delPair('L'); // hibbard deletion O(lgn) Black links Not Balanced
rb->delPair('P');
rb->put('P', 9);
cout << rb->floor('N') << endl;
rb->print_levelorder();
}

Last updated
Was this helpful?