Skip to content

Instantly share code, notes, and snippets.

@cgebe

cgebe/RedBlackTree.h

Created July 23, 2017 20:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save cgebe/4bf66fbb93acb5eaada4fb83fd2fc2c8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save cgebe/4bf66fbb93acb5eaada4fb83fd2fc2c8 to your computer and use it in GitHub Desktop.
Download ZIP
RedBlackTree
Raw
RedBlackTree.h
template<typename T>
class RedBlackTree {
private:
template<typename T>
struct Node
{
int key;
bool red;
T data;
Node<T>* parent;
Node<T>* left;
Node<T>* right;
};
Node<T>* _root;
Node<T>* insert(Node<T>* n, Node<T>* newNode);
void insertFix(Node<T>* n);
bool remove(Node<T>* n);
Node<T>* search(Node<T>* n, int key);
Node<T>* minimum(Node<T>* n);
Node<T>* maximum(Node<T>* n);
int depth(Node<T>* n);
Node<T>* successor(Node<T>* n);
Node<T>* predecessor(Node<T>* n);
void rightRotate(Node<T>* node);
void leftRotate(Node<T>* node);
void printPreOrder(Node<T>* node);
void printInOrder(Node<T>* node);
void printPostOrder(Node<T>* node);
public:
int insert(T data);
int insert(int key, T data);
bool remove(int key);
T search(int key);
T successor(int key);
T predecessor(int key);
int maximum();
int minimum();
int depth();
void printPreOrder();
void printInOrder();
void printPostOrder();
};
template<typename T>
int RedBlackTree<T>::insert(T data)
{
if (_root == nullptr) {
return insert(1, data)->key;
}
else {
return insert(maximum()->key + 1, data)->key;
}
}
template<typename T>
int RedBlackTree<T>::insert(int key, T data)
{
Node<T>* n = new Node<T>();
n->key = key;
n->data = data;
n->red = false;
if (_root == nullptr) {
_root = n;
return _root->key;
}
else {
return insert(_root, n)->key;
}
}
template<typename T>
typename RedBlackTree<T>::Node<T>* RedBlackTree<T>::insert(Node<T>* current, Node<T>* newNode)
{
if (current->key == newNode->key) {
return current;
}
if (current->key > newNode->key) {
if (current->left == nullptr) {
current->left = newNode;
newNode->parent = current;
newNode->red = true;
insertFix(newNode);
return newNode;
}
else {
return insert(current->left, newNode);
}
}
else {
if (current->right == nullptr) {
current->right = newNode;
newNode->parent = current;
newNode->red = true;
insertFix(newNode);
return newNode;
}
else {
return insert(current->right, newNode);
}
}
}
template<typename T>
void RedBlackTree<T>::insertFix(Node<T>* node)
{
while (node->parent != nullptr && node->parent->red) {
if (node->parent->parent->left != nullptr && node->parent->key == node->parent->parent->left->key) {
// left subtree
Node<T>* uncle = node->parent->parent->right;
if (uncle != nullptr && uncle->red) {
node->parent->red = false; // set parent to black
uncle->red = false; // set uncle to black
node->parent->parent->red = true; // set grandparent red
node = node->parent->parent;
}
else {
if (node->parent->right != nullptr && node->key == node->parent->right->key) {
node = node->parent;
leftRotate(node);
}
node->parent->red = false;
node->parent->parent->red = true;
rightRotate(node->parent->parent);
}
}
if (node->parent->parent->right != nullptr && node->parent->key == node->parent->parent->right->key) {
Node<T>* uncle = node->parent->parent->left;
if (uncle != nullptr && uncle->red) {
node->parent->red = false; // set parent to black
uncle->red = false; // set uncle to black
node->parent->parent->red = true; // set grandparent red
node = node->parent->parent;
}
else {
if (node->parent->left != nullptr && node->key == node->parent->left->key) {
node = node->parent;
rightRotate(node);
}
node->parent->red = false;
node->parent->parent->red = true;
leftRotate(node->parent->parent);
}
}
}
_root->red = false;
}
template<typename T>
void RedBlackTree<T>::rightRotate(Node<T>* node)
{
Node<T>* child = node->left;
node->left = child->right;
child->right = node;
if (node->parent != nullptr) {
child->parent = node->parent;
node->parent = child;
if (child->parent->left->key == node->key) {
// left subtree of parent
child->parent->left = child;
}
if (child->parent->right->key == node->key) {
// right subtree of parent
child->parent->right = child;
}
}
else {
node->parent = child;
child->parent = nullptr;
_root = child;
}
}
template<typename T>
void RedBlackTree<T>::leftRotate(Node<T>* node)
{
Node<T>* child = node->right;
node->right = child->left;
child->left = node;
if (node->parent != nullptr) {
child->parent = node->parent;
node->parent = child;
if (child->parent->left->key == node->key) {
// left subtree of parent
child->parent->left = child;
}
if (child->parent->right->key == node->key) {
// right subtree of parent
child->parent->right = child;
}
}
else {
node->parent = child;
child->parent = nullptr;
_root = child;
}
}
template<typename T>
bool RedBlackTree<T>::remove(Node<T>* n)
{
Node<T>* x;
Node<T>* y;
if (node->left == nullptr || node->right == nullptr) {
y = node;
}
else {
y = successor(node);
}
if (y->left != nullptr) {
x = y->left;
}
else {
x = y->right;
}
if (x != nullptr) {
x->parent = y->parent;
}
else {
return false;
}
if (y->parent == nullptr) {
_root = x;
}
else {
if (y->key == y->parent->left->key) {
y->parent->left = x;
}
else {
y->parent->right = x;
}
}
return true;
}
template<typename T>
bool RedBlackTree<T>::remove(int key)
{
return remove(search(key));
}
template<typename T>
T RedBlackTree<T>::search(int key)
{
return search(_root, key)->data;
}
template<typename T>
T RedBlackTree<T>::successor(int key)
{
return successor(search(key))->data;
}
template<typename T>
T RedBlackTree<T>::predecessor(int key)
{
return predecessor(search(key))->data;
}
template<typename T>
typename RedBlackTree<T>::Node<T>* RedBlackTree<T>::search(Node<T>* node, int key)
{
if (node == nullptr || node->key == key) {
return node;
}
if (key < node->key) {
return search(node->left, key);
}
else {
return search(node->right, key);
}
}
template<typename T>
typename RedBlackTree<T>::Node<T>* RedBlackTree<T>::successor(Node<T>* node)
{
if (node->right == nullptr) {
return minimum(node->right);
}
Node<T>* y = node->parent;
while (y != nullptr && node->key == y->right->key) {
node = y;
y = node->parent;
}
return y;
}
template<typename T>
typename RedBlackTree<T>::Node<T>* RedBlackTree<T>::predecessor(Node<T>* node)
{
if (node->left == nullptr) {
return maximum(node->left);
}
Node<T>* y = node->parent;
while (y != nullptr && node->key == y->left->key) {
node = y;
y = node->parent;
}
return y;
}
template<typename T>
int RedBlackTree<T>::maximum()
{
return maximum(_root)->key;
}
template<typename T>
int RedBlackTree<T>::minimum()
{
return minimum(_root)->key;
}
template<typename T>
int RedBlackTree<T>::depth()
{
return depth(_root);
}
template<typename T>
int RedBlackTree<T>::depth(Node<T>* node)
{
if (node == nullptr) {
return 0;
}
if (node->left == nullptr) {
return 1;
}
else {
return depth(node->left) + 1;
}
}
template<typename T>
typename RedBlackTree<T>::Node<T>* RedBlackTree<T>::minimum(Node<T>* node) {
if (node == nullptr || node->left == nullptr) {
return node;
}
else {
return minimum(node->left);
}
}
template<typename T>
typename RedBlackTree<T>::Node<T>* RedBlackTree<T>::maximum(Node<T>* node) {
if (node == nullptr || node->right == nullptr) {
return node;
}
else {
return maximum(node->right);
}
}
template<typename T>
void RedBlackTree<T>::printPreOrder()
{
//OutputDebugString(("root: " + std::to_string(_root->key) + "\n").c_str());
printPreOrder(_root);
}
template<typename T>
void RedBlackTree<T>::printInOrder()
{
printInOrder(_root);
}
template<typename T>
void RedBlackTree<T>::printPostOrder()
{
printPostOrder(_root);
}
template<typename T>
void RedBlackTree<T>::printPreOrder(Node<T>* node) {
if (node != nullptr) {
if (node->parent != nullptr) {
OutputDebugString((std::to_string(node->parent->key) + " (" + std::to_string(node->parent->red) + ") -> " + std::to_string(node->key) + +" (" + std::to_string(node->red) + ")\n").c_str());
}
else {
OutputDebugString(("root: " + std::to_string(node->key) + "\n").c_str());
}
printPreOrder(node->left);
printPreOrder(node->right);
}
}
template<typename T>
void RedBlackTree<T>::printInOrder(Node<T>* node) {
if (node != nullptr) {
printInOrder(node->left);
OutputDebugString((std::to_string(node->key) + "\n").c_str());
printInOrder(node->right);
}
}
template<typename T>
void RedBlackTree<T>::printPostOrder(Node<T>* node) {
if (node != nullptr) {
printPostOrder(node->left);
printPostOrder(node->right);
OutputDebugString((std::to_string(node->key) + "\n").c_str());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment