Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include <bits/stdc++.h> using namespace std; enum{ RED, BLACK, DOUBLE_BLACK }; struct Node{ int data, color; Node *left, *right, *parent; Node(int data){ this->data = data; this->color = RED; left = right = parent = NULL; } }; class RedBlackTree{ private: Node *root; void rotateLeft(Node *node){ Node *right = node->right; node->right = right->left; if(node->right != NULL) node->right->parent = node; right->parent = node->parent; if(node->parent == NULL) root = right; else if(node == node->parent->left) node->parent->left = right; else node->parent->right = right; right->left = node; node->parent = right; } void rotateRight(Node *node){ Node *left = node->left; node->left = left->right; if(node->left != NULL) node->left->parent = node; left->parent = node->parent; if(node->parent == NULL) root = left; else if(node == node->parent->left) node->parent->left = left; else node->parent->right = left; left->right = node; node->parent = left; } void fixInsertion(Node *node){ if(root == node){ node->color = BLACK; return; } while(node->color != BLACK && node->parent->color == RED){ Node *grand_parent = node->parent->parent; //When parent of new node is left child of grandparents of new node if(grand_parent->left == node->parent){ Node *temp = grand_parent->right; //If new node's grand parent right child is red, recolor if(grand_parent->right != NULL && temp->color == RED){ node->parent->color = temp->color = BLACK; grand_parent->color = RED; node = grand_parent; }else{ //If node is right child of its parent, left rotate if(node->parent->right == node){ rotateLeft(node->parent); node = node->parent; } //If node is left child of its parent, right rotate rotateRight(grand_parent); swap(node->parent->color, grand_parent->color); node = node->parent; } //When parent of new node is right child of grandparents of new node }else{ Node *temp = grand_parent->left; //If grandparent left child is red, recolor if(grand_parent->left != NULL && temp->color == RED){ node->parent->color = temp->color = BLACK; grand_parent->color = RED; node = grand_parent; }else{ //If node is left child of its parent, right rotate (Same as right grandparent child case) if(node->parent->left == node){ rotateRight(node); node = node->parent; } //If node is right click of its parent, left rotate rotateLeft(node); swap(node->parent->color, grand_parent->color); node = node->parent; } } root->color = BLACK; } } Node* getSmallestNode(Node *node){ Node *curr = node; while(curr->left != NULL) curr = curr->left; return curr; } //Normal BST delete process Node* deleteValue(Node *root, int target){ if(root == NULL) return root; if(target < root->data) return deleteValue(root->left, target); if(target > root->data) return deleteValue(root->right, target); if(root->left == NULL || root->right == NULL) return root; Node *temp = getSmallestNode(root->right); root->data = temp->data; return deleteValue(root->right, temp->data); } int getColor(Node *node){ if(node == NULL) return BLACK; return node->color; } void fixDeletion(Node *node){ if(node == NULL) return; if(node == root){ root = NULL; return; } if(getColor(node) == RED || getColor(node->left) == RED || getColor(node->right) == RED){ Node *child = node->left != nullptr ? node->left : node->right; if(node == node->parent->left){ node->parent->left = child; if(child != NULL){ child->parent = node->parent; child->color = BLACK; } delete(node); }else{ node->parent->right = child; if(child != NULL){ child->parent = node->parent; child->color = BLACK; } delete(node); } }else{ Node *parent, *sibling, *temp; parent = sibling = NULL; temp = node; temp->color = DOUBLE_BLACK; while(temp != root && getColor(temp) == DOUBLE_BLACK){ parent = temp->parent; if(temp == parent->left){ sibling = parent->right; if(getColor(sibling) == RED){ sibling->color = BLACK; parent->color = RED; rotateLeft(parent); }else{ if(getColor(sibling->left) == BLACK && getColor(sibling->right) == BLACK){ sibling->color = RED; if(getColor(parent) == RED) parent->color = BLACK; else parent->color = DOUBLE_BLACK; temp = parent; }else{ if(getColor(sibling->right) == BLACK){ sibling->left->color = BLACK; sibling->color = RED; rotateRight(sibling); sibling = parent->right; } sibling->color = parent->color; parent->color = sibling->right->color = BLACK; rotateLeft(parent); break; } } }else{ sibling = parent->left; if(getColor(sibling) == RED){ sibling->color = BLACK; parent->color = RED; rotateRight(parent); }else{ if(getColor(sibling->left) == BLACK && getColor(sibling->right) == BLACK){ sibling->color = RED; if(getColor(parent) == RED) parent->color = BLACK; else parent->color = DOUBLE_BLACK; temp = parent; }else{ if(getColor(sibling->left) == BLACK){ sibling->right->color = BLACK; sibling->color = RED; rotateLeft(sibling); sibling = parent->left; } sibling->color = parent->color; parent->color = sibling->left->color = BLACK; rotateRight(parent); break; } } } } if(node == node->parent->left) node->parent->left = NULL; else node->parent->right = NULL; delete(node); root->color = BLACK; } } public: RedBlackTree(){ this->root = NULL; } void insertNode(int data){ Node *node = new Node(data); if(root == NULL){ this->root = node; }else{ Node *curr = root, *parent; while(curr != NULL){ parent = curr; if(curr->data < data) curr = curr->right; else curr = curr->left; } node->parent = parent; if(parent->data < data) parent->right = node; else parent->left = node; } fixInsertion(node); } void deleteNode(int target){ Node *node = deleteValue(root, target); fixDeletion(node); } void searchNode(int target){ Node *curr = root; while(curr->data != target){ if(curr->data < target){ curr = curr->right; }else{ curr = curr->left; } } printf("Color of Node %d : %s\n", target, (curr->color == BLACK ? "BLACK" : "RED")); } }; int main(){ RedBlackTree tree; tree.insertNode(7); tree.insertNode(6); tree.insertNode(5); tree.insertNode(4); tree.insertNode(3); tree.insertNode(2); tree.insertNode(1); tree.deleteNode(4); tree.deleteNode(3); tree.searchNode(6); return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)
