C++ Data Structures with Templates
Chapter 7: Red-Black Tree
The Code
A C Implementationenum Colour { RED = 1, BLACK };
struct rbNode {
uint8_t key; // which is the square on the board
uint8_t colour;
rbNode *left, *right, *parent;
void* data;
};
rbNode* root;
void doInsert(uint8_t key, cBoard* square) {
rbNode* temp = makeNode(key, square);
root = rbInsert(temp, root);
postInsertFix(temp, root);
}
rbNode* makeNode(uint8_t key, cBoard* square) {
rbNode* temp = (rbNode*)malloc(sizeof(rbNode));
temp->key = key;
temp->left = temp->right = temp->parent = NULL;
temp->colour = RED;
temp->data = malloc(sizeof(cBoard));
memcpy(temp->data, square, sizeof(cBoard));
return temp;
}
rbNode* rbInsert(rbNode* node, rbNode* leaf) {
if (leaf == NULL) {
return node;
}
if (node->key == leaf->key) {
// could implement update here
return leaf;
}
if (node->key < leaf->key) {
leaf->left = rbInsert(node, leaf->left);
leaf->left->parent = leaf;
}
else if (node->key > leaf->key) {
leaf->right = rbInsert(node, leaf->right);
leaf->right->parent = leaf;
}
return leaf;
}
void postInsertFix(rbNode *&node, rbNode *&root) {
rbNode* grandMa = NULL;
rbNode* aunty = NULL;
while (node != root && node->parent->colour == RED) {
grandMa = node->parent->parent;
if (node->parent == grandMa->left) {
aunty = grandMa->right;
if (aunty && aunty->colour == RED) {
node->parent->colour = BLACK;
aunty->colour = BLACK;
grandMa->colour = RED;
node = grandMa;
}
else {
if (node == node->parent->right) {
node = node->parent;
rbRotateLeft(node, root);
}
node->parent->colour = BLACK;
grandMa->colour = RED;
rbRotateRight(grandMa, root);
}
}
else {
aunty = grandMa->left;
if (aunty && aunty->colour == RED) {
node->parent->colour = BLACK;
aunty->colour = BLACK;
grandMa->colour = RED;
node = grandMa;
}
else {
if (node == node->parent->left) {
node = node->parent;
rbRotateRight(node, root);
}
node->parent->colour = BLACK;
grandMa->colour = RED;
rbRotateLeft(grandMa, root);
}
}
}
root->colour = BLACK;
}
void rbSwap(uint8_t* a, uint8_t* b) {
// C++ has a swap template class but this version is C
// so good old xor swap does the job
*a = *a ^ *b;
*b = *a ^ *b;
*a = *b ^ *a;
}
void rbRotateLeft(rbNode* node, rbNode*& root) {
rbNode* child = node->right;
node->right = child->left;
if (child->left) {
child->left->parent = node;
}
child->parent = node->parent;
if (node == root) {
root = child;
}
else if (node == node->parent->left) {
node->parent->left = child;
}
else {
node->parent->right = child;
}
child->left = node;
node->parent = child;
}
void rbRotateRight(rbNode* node, rbNode*& root) {
rbNode* child = node->left;
node->left = child->right;
if (child->right != NULL) {
child->right->parent = node;
}
child->parent = node->parent;
if (node == root) {
root = child;
}
else if (node == node->parent->right) {
node->parent->right = child;
}
else {
node->parent->left = child;
}
child->right = node;
node->parent = child;
}
int rbHeight(rbNode* leaf) {
if (leaf) {
int subMax = rbMax(rbHeight(leaf->left), rbHeight(leaf->right));
if (leaf->colour == BLACK) { subMax++; }
return subMax;
}
return 0;
}
int rbMax(int a, int b) {
return (a <= b) ? b : a;
}
cBoard* rbSearch(uint8_t key, rbNode* leaf) {
if (leaf) {
if (leaf->key == key) {
return (cBoard*)leaf->data;
}
if (key < leaf->key) {
return rbSearch(key, leaf->left);
}
return rbSearch(key, leaf->right);
}
return NULL;
}
rbNode* rbFind(uint8_t key, rbNode* leaf) {
if (leaf) {
if (leaf->key == key) {
return leaf;
}
if (key < leaf->key) {
return rbFind(key, leaf->left);
}
return rbFind(key, leaf->right);
}
return NULL;
}
void rbDeleteTree(rbNode* leaf) {
if (leaf) {
rbDeleteTree(leaf->left);
rbDeleteTree(leaf->right);
free(leaf->data);
free(leaf);
}
}
void rbDoDelete(uint8_t key) {
rbNode* found = rbFind(key, root);
if (found) {
rbNode* del = rbPreDeleteFix(found, root);
// now zap whatever is no longer needed
free(del->data);
free(del);
}
}
rbNode* rbPreDeleteFix(rbNode* node, rbNode*& root) {
rbNode* nodeToDelete = node;
rbNode* child = NULL;
rbNode* parentNode = NULL;
if (nodeToDelete->left == NULL) { // node has one or no children
child = nodeToDelete->right; // which might be NULL
}
else {
if (nodeToDelete->right == NULL) // node has one child
child = nodeToDelete->left; // child is not NULL
else { // node has two children
nodeToDelete = rbMinimum(nodeToDelete->right);
// so we reset to the minimum key node
// from the right child (so next largest key)
child = nodeToDelete->right;
}
}
if (nodeToDelete != node) {
// if the nodeToDelete got changed above
node->left->parent = nodeToDelete;
nodeToDelete->left = node->left;
if (nodeToDelete != node->right) {
parentNode = nodeToDelete->parent;
if (child) {
child->parent = nodeToDelete->parent;
}
nodeToDelete->parent->left = child;
nodeToDelete->right = node->right;
node->right->parent = nodeToDelete;
}
else {
parentNode = nodeToDelete;
}
if (root == node) {
root = nodeToDelete;
}
else if (node->parent->left == node) {
node->parent->left = nodeToDelete;
}
else {
node->parent->right = nodeToDelete;
}
nodeToDelete->parent = node->parent;
rbSwap(&nodeToDelete->colour, &node->colour);// using xor swap
nodeToDelete = node;
// nodeToDelete now definately points to node to be deleted
}
else {
parentNode = nodeToDelete->parent;
if (child) {
child->parent = nodeToDelete->parent;
}
if (root == node) {
root = child;
}
else {
if (node->parent->left == node) {
node->parent->left = child;
}
else {
node->parent->right = child;
}
}
}
if (nodeToDelete->colour != RED) {
while (child != root && (child == NULL || child->colour == BLACK)) {
if (child == parentNode->left) {
rbNode* sisterNode = parentNode->right;
if (sisterNode->colour == RED) {
sisterNode->colour = BLACK;
parentNode->colour = RED;
rbRotateLeft(parentNode, root);
sisterNode = parentNode->right;
}
if ((sisterNode->left == NULL ||
sisterNode->left->colour == BLACK) &&
(sisterNode->right == NULL ||
sisterNode->right->colour == BLACK)) {
sisterNode->colour = RED;
child = parentNode;
parentNode = parentNode->parent;
}
else {
if (sisterNode->right == NULL ||
sisterNode->right->colour == BLACK) {
if (sisterNode->left) sisterNode->left->colour = BLACK;
sisterNode->colour = RED;
rbRotateRight(sisterNode, root);
sisterNode = parentNode->right;
}
sisterNode->colour = parentNode->colour;
parentNode->colour = BLACK;
if (sisterNode->right) {
sisterNode->right->colour = BLACK;
}
rbRotateLeft(parentNode, root);
break;
}
}
else { // same as above but the other way about
rbNode* sisterNode = parentNode->left;
if (sisterNode->colour == RED) {
sisterNode->colour = BLACK;
parentNode->colour = RED;
rbRotateRight(parentNode, root);
sisterNode = parentNode->left;
}
if ((sisterNode->right == NULL ||
sisterNode->right->colour == BLACK) &&
(sisterNode->left == NULL ||
sisterNode->left->colour == BLACK)) {
sisterNode->colour = RED;
child = parentNode;
parentNode = parentNode->parent;
}
else {
if (sisterNode->left == NULL ||
sisterNode->left->colour == BLACK) {
if (sisterNode->right) {
sisterNode->right->colour = BLACK;
}
sisterNode->colour = RED;
rbRotateLeft(sisterNode, root);
sisterNode = parentNode->left;
}
sisterNode->colour = parentNode->colour;
parentNode->colour = BLACK;
if (sisterNode->left) {
sisterNode->left->colour = BLACK;
}
rbRotateRight(parentNode, root);
break;
}
}
}
if (child) {
child->colour = BLACK;
}
}
return nodeToDelete;
}
rbNode* rbMaximum(rbNode* node) {
while (node->right) {
node = node->right;
}
return node;
}
rbNode* rbMinimum(rbNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
void treeKeyPrint(rbNode* root) {
if (root) {
cout << "root: " << root->key << '\n';
if (root->left) {
cout << "root Left: " << root->left->key;
}
if (root->right) {
cout << "root Right: " << root->right->key;
}
cout << '\n';
}
}
void levelOrderHelper(rbNode* root)
{
if (root == NULL)
return;
queue<rbNode*> q;
q.push(root);
while (!q.empty())
{
rbNode *temp = q.front();
cout << temp->key << " ";
q.pop();
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
main() Demo Code
#include "stdafx.h"
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
using namespace std;
enum Players { WHT, BLK };
uint8_t nextMove = WHT;
enum Pieces { PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING };
char pNames[][7] = { "Pawn", "Rook", "Knight", "Bishop", "Queen", "King" };
char pSymbol[] = { 'P', 'R', 'N', 'B', 'Q', 'K' };
struct cBoard {
uint8_t player;
uint8_t piece;
};
typedef void(*ClBk)(uint8_t, struct cBoard*);
typedef void(*ClBkC)(uint8_t, uint8_t, cBoard*);
void displayBoard();
void doInsert(uint8_t, cBoard*);
rbNode* makeNode(uint8_t, cBoard*);
rbNode* rbInsert(rbNode*, rbNode*);
void postInsertFix(rbNode *&, rbNode *&);
void rbSwap(uint8_t*, uint8_t*);
void rbRotateLeft(rbNode*, rbNode *&);
void rbRotateRight(rbNode*, rbNode *&);
int rbHeight(rbNode*);
int rbMax(int a, int b);
cBoard* rbSearch(uint8_t, rbNode*);
rbNode* rbFind(uint8_t, rbNode*);
void rbDeleteTree(rbNode*);
rbNode* rbMaximum(rbNode*);
rbNode* rbMinimum(rbNode*);
rbNode* rbPreDeleteFix(rbNode*, rbNode*&);
void rbDoDelete(uint8_t);
void levelOrderHelper(rbNode*);
void treeKeyPrint(rbNode*);
void setupBoard();
void makeMove(uint8_t,uint8_t);
void castleMove(uint8_t, uint8_t, uint8_t, uint8_t);
void playGame();
int main()
{
setupBoard();
displayBoard();
playGame();
cin.get();
return 0;
}
void makeMove(uint8_t from, uint8_t to) {
cBoard* fSquare = rbSearch(from, root);
cBoard* tSquare = rbSearch(to, root);
if (fSquare) {
if (fSquare->player == nextMove) {
if (tSquare == NULL || tSquare->player != nextMove) {
// probably a valid move but you could write a lot more
// validation to check route is clear if not knight and
// distance allowed and from and to not the same etc.
if (tSquare) {
rbDoDelete(to);
}
doInsert(to, fSquare);
rbDoDelete(from);
}
else {
cout << "Target square invalid\n";
}
}
else {
cout << "Not your move\n";
}
}
nextMove = (nextMove == WHT) ? BLK : WHT; //whose move next
displayBoard();
}
// OK the castle move needs different validation so
// as this is not intended as a chess playing game demo
// this function is a bodge to allow the move
void castleMove(uint8_t f1, uint8_t f2, uint8_t t1, uint8_t t2) {
cBoard* f1Square = rbSearch(f1, root);
cBoard* f2Square = rbSearch(f2, root);
doInsert(t1, f1Square);
rbDoDelete(f1);
doInsert(t2, f2Square);
rbDoDelete(f2);
nextMove = (nextMove == WHT) ? BLK : WHT; //whose move next
displayBoard();
}
void playGame() {
uint8_t cOpt = 0;
uint8_t moves[][2] = { { 13,29 },{ 53,37 },{ 7,13 },{ 58,43 },{ 2,19 },{ 62,35 },
{ 13,23 },{ 52,44 },{ 12,20 },{ 63,46 },{ 3,39 },{ 59,45 },{ 23,40 },{ 0,0 },
{ 19,36 },{ 46,29 },{ 39,60 },{ 35,14 },{ 5,13 },{ 45,31 } };
uint8_t cstlmoves[][4] = { { 61,64,63,62 } };
for (int i = 0; i < sizeof(moves) / 2; i++) {
if (moves[i][0] == 0) {
castleMove(cstlmoves[cOpt][0], cstlmoves[cOpt][1], cstlmoves[cOpt][2], cstlmoves[cOpt][3]);
cOpt++; // max is 2 per game
}
else {
makeMove(moves[i][0], moves[i][1]);
}
}
cout << "Checkmate!\n";
}
void setupBoard() {
cBoard wSquare = { WHT, PAWN }, bSquare = { BLK, PAWN };
for (int i = 1; i < 9; i++) {
wSquare.piece = bSquare.piece = PAWN;
doInsert(i + 8, &wSquare);
doInsert(i + 48, &bSquare);
switch (i) {
case 1:
case 8:
wSquare.piece = bSquare.piece = ROOK;
break;
case 2:
case 7:
wSquare.piece = bSquare.piece = KNIGHT;
break;
case 3:
case 6:
wSquare.piece = bSquare.piece = BISHOP;
break;
case 4:
wSquare.piece = bSquare.piece = QUEEN;
break;
case 5:
wSquare.piece = bSquare.piece = KING;
break;
}
doInsert(i, &wSquare);
doInsert(i + 56, &bSquare);
}
}
void displayBoard() {
cBoard* square;
for (int i = 0; i < 8; i++) {
for (int j = 1; j < 9; j++) {
square = rbSearch(j + i * 8, root);
if (square) {
cout << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece] + 32));
}
else {
cout << ' ';
}
}
cout << '\n';
}
}
setup() Demo Code
enum Players {WHT, BLK};
uint8_t nextMove = WHT;
enum Pieces {PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING};
char pNames[][7] = {"Pawn", "Rook", "Knight", "Bishop", "Queen", "King"};
char pSymbol[] = {'P', 'R', 'N', 'B', 'Q', 'K'};
struct cBoard{
uint8_t player;
uint8_t piece;
};
typedef void (*ClBk)(uint8_t, struct cBoard*);
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
Serial.begin(115200);
Serial << freeRam() << '\n';
setupBoard();
Serial << freeRam() << '\n';
displayBoard();
Serial << "Black Height: " << rbHeight(root) << '\n';
playGame();
Serial << "Black Height: " << rbHeight(root) << '\n';
rbIterate(root, printSquares);
rbDeleteTree(root);
Serial << freeRam() << '\n';
}
void printSquares(uint8_t key, cBoard* square) {
Serial << "Square " << key << ": Player: " << (square->player == WHT ? "White" : "Black") << " Piece: " << pNames[square->piece] << '\n';
}
void playGame() {
// This game was played between London and Athens in 1897
// London fell into a neat trap and lost to Athens in 10 moves each.
uint8_t moves[][2] = {{13,29},{53,37},{7,13},{58,43},{2,19},{62,35},
{13,23},{52,44},{12,20},{63,46},{3,39},{59,45},{23,40},{0,0},
{19,36},{46,29},{39,60},{35,14},{5,13},{45,31}};
uint8_t cstlmoves[][4] = {{61,64,63,62}};
for (int i = 0; i < sizeof(moves) / 2; i++) {
if(moves[i][0] == 0) {
// cludge to support castling (feel free to tweak and validate)
makeMove(64, 62);
makeMove(61, 63);
} else {
makeMove(moves[i][0], moves[i][1]);
}
nextMove = (nextMove == WHT)? BLK : WHT; //whose move next
displayBoard();
}
Serial << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
cBoard* fSquare = rbSearch(from, root);
cBoard* tSquare = rbSearch(to, root);
if(fSquare) {
if(fSquare->player == nextMove) {
if(tSquare == NULL || tSquare->player != nextMove) {
// probably a valid move but you could write a lot more
// validation to check route is clear if not knight and
// distance allowed and from and to not the same etc.
if(tSquare) {
rbDoDelete(to);
}
rbDoInsert(to, fSquare);
rbDoDelete(from);
} else {
Serial << "Target square invalid\n";
}
} else {
Serial << "Not your move\n";
}
}
}
void setupBoard() {
cBoard wSquare = {WHT, PAWN}, bSquare = {BLK, PAWN};
for(int i = 1; i < 9; i++) {
wSquare.piece = bSquare.piece = PAWN;
rbDoInsert(i + 8, &wSquare);
rbDoInsert(i + 48, &bSquare);
switch(i) {
case 1:
case 8:
wSquare.piece = bSquare.piece = ROOK;
break;
case 2:
case 7:
wSquare.piece = bSquare.piece = KNIGHT;
break;
case 3:
case 6:
wSquare.piece = bSquare.piece = BISHOP;
break;
case 4:
wSquare.piece = bSquare.piece = QUEEN;
break;
case 5:
wSquare.piece = bSquare.piece = KING;
break;
}
rbDoInsert(i, &wSquare);
rbDoInsert(i + 56, &bSquare);
}
}
void displayBoard() {
cBoard* square;
for(int i = 0; i < 8; i++) {
for(int j = 1; j < 9; j++) {
square = rbSearch(j + i * 8, root);
if(square) {
Serial << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece]+32));
}else {
Serial << ' ';
}
}
Serial << '\n';
}
Serial << '\n';
}
RedBlack.h
#ifndef RedBlack_h
#define RedBlack_h
// std::swap is available in this context
//template <class T> inline void swap(T& a, T& b)
//{
// T c(a); a = b; b = c;
//};
template<typename T, typename K>
class RedBlack {
public:
using RBIter = bool(*)(K, T*);
RedBlack(bool = false);
~RedBlack();
bool deleteNode(K);
bool insertNode(K, T*);
int blackHeight();
int nodeCount(bool);
T* nodeSearch(K);
void iterate(RBIter);
void reverseIterate(RBIter);
private:
enum Colour { RED, BLACK };
struct rbNode {
K key;
uint8_t colour;
rbNode *left, *right, *parent;
void* data;
};
rbNode* root;
uint8_t tSize;
uint8_t nodeSize;
bool memoryError;
bool updateOK;
bool rbRepeat;
T* rbSearch(K, rbNode*);
int rbCount(bool, rbNode*);
rbNode* rbMinimum(rbNode*);
rbNode* rbMaximum(rbNode*);
int rbHeight(rbNode*);
int rbMax(int, int);
rbNode* rbFind(K, rbNode*);
void rbDeleteTree(rbNode*);
void rbRotateRight(rbNode*, rbNode*&);
void rbRotateLeft(rbNode*, rbNode*&);
rbNode* rbPreDeleteFix(rbNode*, rbNode*&);
void rbPostInsertFix(rbNode*, rbNode*&);
rbNode* rbInsert(rbNode*, rbNode*);
rbNode* rbMakeNode(K key, T* data);
void rbIterate(rbNode*, RBIter);
void rbRevIterate(rbNode*, RBIter);
};
// Constructot / destructor
template<typename T, typename K>
RedBlack<T, K>::RedBlack(bool noUpdates = false) {
root = NULL;
nodeSize = sizeof(rbNode);
tSize = sizeof(T);
updateOK = !noUpdates;
}
template<typename T, typename K>
RedBlack<T, K>::~RedBlack() {
rbDeleteTree(root);
}
template<typename T, typename K>
bool RedBlack<T, K>::insertNode(K key, T* data) {
memoryError = false;
rbNode* temp = rbMakeNode(key, data);
root = rbInsert(temp, root);
rbPostInsertFix(temp, root);
return memoryError;
}
template<typename T, typename K>
bool RedBlack<T, K>::deleteNode(K key) {
rbNode* found = rbFind(key, root);
if (found) {
rbNode* del = rbPreDeleteFix(found, root);
free(del->data);
free(del);
return true;
}
return false;
}
template<typename T, typename K>
T* RedBlack<T, K>::nodeSearch(K key) {
return rbSearch(key, root);
}
template<typename T, typename K>
void RedBlack<T, K>::iterate(RBIter callBack) {
rbRepeat = true;
rbIterate(root, callBack);
}
template<typename T, typename K>
void RedBlack<T, K>::reverseIterate(RBIter callBack) {
rbRepeat = true;
rbRevIterate(root, callBack);
}
template<typename T, typename K>
int RedBlack<T, K>::blackHeight() {
return rbHeight(root);
}
template<typename T, typename K>
int RedBlack<T, K>::nodeCount(bool blackOnly) {
return rbCount(blackOnly, root);
}
//private methods
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbMakeNode(K key, T* data) {
rbNode* temp = (rbNode*)malloc(nodeSize);
if (temp == NULL) {
memoryError = true;
}
temp->key = key;
temp->left = temp->right = temp->parent = NULL;
temp->colour = RED;
temp->data = malloc(tSize);
if (temp->data) {
memcpy(temp->data, data, tSize);
}
else {
memoryError = true;
}
return temp;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbInsert(rbNode* node, rbNode* leaf) {
if (leaf == NULL) {
return node;
}
if (node->key == leaf->key) {
if (updateOK) {
memcpy(leaf->data, node->data, tSize);
free(node->data);
free(node);
}
else {
memoryError = true; // well sort of
}
return leaf;
}
if (node->key < leaf->key) {
leaf->left = rbInsert(node, leaf->left);
leaf->left->parent = leaf;
}
else if (node->key > leaf->key) {
leaf->right = rbInsert(node, leaf->right);
leaf->right->parent = leaf;
}
return leaf;
}
template<typename T, typename K>
void RedBlack<T, K>::rbPostInsertFix(rbNode* node, rbNode*& root) {
rbNode* grandMa = NULL;
rbNode* aunty = NULL;
while (node != root && node->parent->colour == RED) {
grandMa = node->parent->parent;
if (node->parent == grandMa->left) {
aunty = grandMa->right;
if (aunty && aunty->colour == RED) {
node->parent->colour = BLACK;
aunty->colour = BLACK;
grandMa->colour = RED;
node = grandMa;
}
else {
if (node == node->parent->right) {
node = node->parent;
rbRotateLeft(node, root);
}
node->parent->colour = BLACK;
grandMa->colour = RED;
rbRotateRight(grandMa, root);
}
}
else {
aunty = grandMa->left;
if (aunty && aunty->colour == RED) {
node->parent->colour = BLACK;
aunty->colour = BLACK;
grandMa->colour = RED;
node = grandMa;
}
else {
if (node == node->parent->left) {
node = node->parent;
rbRotateRight(node, root);
}
node->parent->colour = BLACK;
grandMa->colour = RED;
rbRotateLeft(grandMa, root);
}
}
}
root->colour = BLACK;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbFind(K key, rbNode* leaf) {
if (leaf) {
if (leaf->key == key) {
return leaf;
}
if (key < leaf->key) {
return rbFind(key, leaf->left);
}
return rbFind(key, leaf->right);
}
return NULL;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbPreDeleteFix(rbNode* node, rbNode*& root) {
rbNode* nodeToDelete = node;
rbNode* child = NULL;
rbNode* parentNode = NULL;
if (nodeToDelete->left == NULL) { // node has one or no children
child = nodeToDelete->right; // which might be NULL
}
else {
if (nodeToDelete->right == NULL) // node has one child
child = nodeToDelete->left; // child is not NULL
else { // node has two children
nodeToDelete = rbMinimum(nodeToDelete->right);
// so we reset to the minimum key node
// from the right child (so next largest key)
child = nodeToDelete->right;
}
}
if (nodeToDelete != node) {
// if the nodeToDelete got changed above
node->left->parent = nodeToDelete;
nodeToDelete->left = node->left;
if (nodeToDelete != node->right) {
parentNode = nodeToDelete->parent;
if (child) {
child->parent = nodeToDelete->parent;
}
nodeToDelete->parent->left = child;
nodeToDelete->right = node->right;
node->right->parent = nodeToDelete;
}
else {
parentNode = nodeToDelete;
}
if (root == node) {
root = nodeToDelete;
}
else if (node->parent->left == node) {
node->parent->left = nodeToDelete;
}
else {
node->parent->right = nodeToDelete;
}
nodeToDelete->parent = node->parent;
swap(nodeToDelete->colour, node->colour);
nodeToDelete = node;
// nodeToDelete now deinately points to node to be deleted
}
else {
parentNode = nodeToDelete->parent;
if (child) {
child->parent = nodeToDelete->parent;
}
if (root == node) {
root = child;
}
else {
if (node->parent->left == node) {
node->parent->left = child;
}
else {
node->parent->right = child;
}
}
}
if (nodeToDelete->colour != RED) {
while (child != root && (child == NULL || child->colour == BLACK)) {
if (child == parentNode->left) {
rbNode* sisterNode = parentNode->right;
if (sisterNode->colour == RED) {
sisterNode->colour = BLACK;
parentNode->colour = RED;
rbRotateLeft(parentNode, root);
sisterNode = parentNode->right;
}
if ((sisterNode->left == NULL ||
sisterNode->left->colour == BLACK) &&
(sisterNode->right == NULL ||
sisterNode->right->colour == BLACK)) {
sisterNode->colour = RED;
child = parentNode;
parentNode = parentNode->parent;
}
else {
if (sisterNode->right == NULL ||
sisterNode->right->colour == BLACK) {
if (sisterNode->left) sisterNode->left->colour = BLACK;
sisterNode->colour = RED;
rbRotateRight(sisterNode, root);
sisterNode = parentNode->right;
}
sisterNode->colour = parentNode->colour;
parentNode->colour = BLACK;
if (sisterNode->right) {
sisterNode->right->colour = BLACK;
}
rbRotateLeft(parentNode, root);
break;
}
}
else { // same as above but the other way about
rbNode* sisterNode = parentNode->left;
if (sisterNode->colour == RED) {
sisterNode->colour = BLACK;
parentNode->colour = RED;
rbRotateRight(parentNode, root);
sisterNode = parentNode->left;
}
if ((sisterNode->right == NULL ||
sisterNode->right->colour == BLACK) &&
(sisterNode->left == NULL ||
sisterNode->left->colour == BLACK)) {
sisterNode->colour = RED;
child = parentNode;
parentNode = parentNode->parent;
}
else {
if (sisterNode->left == NULL ||
sisterNode->left->colour == BLACK) {
if (sisterNode->right) {
sisterNode->right->colour = BLACK;
}
sisterNode->colour = RED;
rbRotateLeft(sisterNode, root);
sisterNode = parentNode->left;
}
sisterNode->colour = parentNode->colour;
parentNode->colour = BLACK;
if (sisterNode->left) {
sisterNode->left->colour = BLACK;
}
rbRotateRight(parentNode, root);
break;
}
}
}
if (child) {
child->colour = BLACK;
}
}
return nodeToDelete;
}
template<typename T, typename K>
void RedBlack<T, K>::rbRotateLeft(rbNode* node, rbNode*& root) {
rbNode* child = node->right;
node->right = child->left;
if (child->left) {
child->left->parent = node;
}
child->parent = node->parent;
if (node == root) {
root = child;
}
else if (node == node->parent->left) {
node->parent->left = child;
}
else {
node->parent->right = child;
}
child->left = node;
node->parent = child;
}
template<typename T, typename K>
void RedBlack<T, K>::rbRotateRight(rbNode* node, rbNode*& root) {
rbNode* child = node->left;
node->left = child->right;
if (child->right != 0) {
child->right->parent = node;
}
child->parent = node->parent;
if (node == root) {
root = child;
}
else if (node == node->parent->right) {
node->parent->right = child;
}
else {
node->parent->left = child;
}
child->right = node;
node->parent = child;
}
template<typename T, typename K>
T* RedBlack<T, K>::rbSearch(K key, rbNode* leaf) {
if (leaf) {
if (leaf->key == key) {
return (T*)leaf->data;
}
if (key < leaf->key) {
return rbSearch(key, leaf->left);
}
return rbSearch(key, leaf->right);
}
return NULL;
}
template<typename T, typename K>
void RedBlack<T, K>::rbIterate(rbNode* leaf, RBIter callBack) {
if (leaf && rbRepeat) {
rbIterate(leaf->left, callBack);
if (rbRepeat) {
rbRepeat = callBack(leaf->key, (T*)leaf->data);
rbIterate(leaf->right, callBack);
}
}
}
template<typename T, typename K>
void RedBlack<T, K>::rbRevIterate(rbNode* leaf, RBIter callBack) {
if (leaf && rbRepeat) {
rbRevIterate(leaf->right, callBack);
if (rbRepeat) {
rbRepeat = callBack(leaf->key, (T*)leaf->data);
rbRevIterate(leaf->left, callBack);
}
}
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbMinimum(rbNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbMaximum(rbNode* node) {
while (node->right) {
node = node->right;
}
return node;
}
template<typename T, typename K>
int RedBlack<T, K>::rbHeight(rbNode* leaf) {
if (leaf) {
int subMax = rbMax(rbHeight(leaf->left), rbHeight(leaf->right));
if (leaf->colour == BLACK) { subMax++; }
return subMax;
}
return 0;
}
template<typename T, typename K>
int RedBlack<T, K>::rbMax(int a, int b) {
return (a <= b) ? b : a;
}
template<typename T, typename K>
int RedBlack<T, K>::rbCount(bool blackOnly, rbNode* leaf) {
if (leaf) {
int rVal = 1;
if (blackOnly && leaf->colour == RED) { rVal--; }
return rVal + rbCount(blackOnly, leaf->left) + rbCount(blackOnly, leaf->right);
}
return 0;
}
template<typename T, typename K>
void RedBlack<T, K>::rbDeleteTree(rbNode* leaf) {
if (leaf) {
rbDeleteTree(leaf->left);
rbDeleteTree(leaf->right);
free(leaf->data);
free(leaf);
}
}
#endif
RedBlack.cpp
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "RedBlack.h"
#include <iostream>
using namespace std;
enum Players { WHT, BLK };
uint8_t nextMove = WHT;
enum Pieces { PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING };
char pNames[][7] = { "Pawn", "Rook", "Knight", "Bishop", "Queen", "King" };
char pSymbol[] = { 'P', 'R', 'N', 'B', 'Q', 'K' };
struct cBoard {
uint8_t player;
uint8_t piece;
};
bool printSquares(uint8_t, cBoard*);
void playGame();
void makeMove(uint8_t, uint8_t);
void setupBoard();
void displayBoard();
RedBlack<cBoard, uint8_t> rbTree(true);
int main()
{
setupBoard();
displayBoard();
playGame();
rbTree.iterate(printSquares);
cout << rbTree.nodeCount(false) << " Total nodes\n";
cout << rbTree.nodeCount(true) << " Black nodes\n";
cout << "Black Height: " << rbTree.blackHeight() << '\n';
rbTree.reverseIterate(printSquares);
cin.get();
return 0;
}
bool printSquares(uint8_t key, cBoard* square) {
// cast the uint8_t as otherwise it is treated as a char by cout
cout << "Square " << (int)key << ": Player: " << (square->player == WHT ? "White" : "Black") << " Piece: " << pNames[square->piece] << '\n';
return true;
}
void playGame() {
// This game was played between London and Athens in 1897
// London fell into a neat trap and lost to Athens in 10 moves each.
uint8_t moves[][2] = { { 13,29 },{ 53,37 },{ 7,13 },{ 58,43 },{ 2,19 },{ 62,35 },
{ 13,23 },{ 52,44 },{ 12,20 },{ 63,46 },{ 3,39 },{ 59,45 },{ 23,40 },{ 0,0 },
{ 19,36 },{ 46,29 },{ 39,60 },{ 35,14 },{ 5,13 },{ 45,31 } };
uint8_t cstlmoves[][4] = { { 61,64,63,62 } };
for (int i = 0; i < sizeof(moves) / 2; i++) {
if (moves[i][0] == 0) {
// cludge to support castling (feel free to tweak and validate)
makeMove(64, 62);
makeMove(61, 63);
}
else {
makeMove(moves[i][0], moves[i][1]);
}
nextMove = (nextMove == WHT) ? BLK : WHT; //whose move next
displayBoard();
}
cout << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
cBoard* fSquare = rbTree.nodeSearch(from);
cBoard* tSquare = rbTree.nodeSearch(to);
if (fSquare) {
if (fSquare->player == nextMove) {
if (tSquare == NULL || tSquare->player != nextMove) {
// probably a valid move but you could write a lot more
// validation to check route is clear if not knight and
// distance allowed and from and to not the same etc.
if (tSquare) {
rbTree.deleteNode(to);
}
rbTree.insertNode(to, fSquare);
rbTree.deleteNode(from);
}
else {
cout << "Target square invalid\n";
}
}
else {
cout << "Not your move\n";
}
}
}
void setupBoard() {
cBoard wSquare = { WHT, PAWN }, bSquare = { BLK, PAWN };
for (int i = 1; i < 9; i++) {
wSquare.piece = bSquare.piece = PAWN;
rbTree.insertNode(i + 8, &wSquare);
rbTree.insertNode(i + 48, &bSquare);
switch (i) {
case 1:
case 8:
wSquare.piece = bSquare.piece = ROOK;
break;
case 2:
case 7:
wSquare.piece = bSquare.piece = KNIGHT;
break;
case 3:
case 6:
wSquare.piece = bSquare.piece = BISHOP;
break;
case 4:
wSquare.piece = bSquare.piece = QUEEN;
break;
case 5:
wSquare.piece = bSquare.piece = KING;
break;
}
rbTree.insertNode(i, &wSquare);
rbTree.insertNode(i + 56, &bSquare);
}
}
void displayBoard() {
cBoard* square;
for (int i = 0; i < 8; i++) {
for (int j = 1; j < 9; j++) {
square = rbTree.nodeSearch(j + i * 8);
if (square) {
cout << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece] + 32));
}
else {
cout << ' ';
}
}
cout << '\n';
}
cout << '\n';
}
RedBlack.ino
#include "RedBlack.h"
enum Players {WHT, BLK};
uint8_t nextMove = WHT;
enum Pieces {PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING};
char pNames[][7] = {"Pawn", "Rook", "Knight", "Bishop", "Queen", "King"};
char pSymbol[] = {'P', 'R', 'N', 'B', 'Q', 'K'};
struct cBoard{
uint8_t player;
uint8_t piece;
};
RedBlack<cBoard, uint8_t> rbTree(true);
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
Serial.begin(115200);
setupBoard();
displayBoard();
playGame();
rbTree.iterate(printSquares);
Serial << rbTree.nodeCount(false) << " Total nodes\n";
Serial << rbTree.nodeCount(true) << " Black nodes\n";
Serial << "Black Height: " << rbTree.blackHeight() << '\n';
rbTree.reverseIterate(printSquares);
}
bool printSquares(uint8_t key, cBoard* square) {
Serial << "Square " << key << ": Player: " << (square->player == WHT ? "White" : "Black") << " Piece: " << pNames[square->piece] << '\n';
return true;
}
void playGame() {
// This game was played between London and Athens in 1897
// London fell into a neat trap and lost to Athens in 10 moves each.
uint8_t moves[][2] = {{13,29},{53,37},{7,13},{58,43},{2,19},{62,35},
{13,23},{52,44},{12,20},{63,46},{3,39},{59,45},{23,40},{0,0},
{19,36},{46,29},{39,60},{35,14},{5,13},{45,31}};
uint8_t cstlmoves[][4] = {{61,64,63,62}};
for (int i = 0; i < sizeof(moves) / 2; i++) {
if(moves[i][0] == 0) {
// cludge to support castling (feel free to tweak and validate)
makeMove(64, 62);
makeMove(61, 63);
} else {
makeMove(moves[i][0], moves[i][1]);
}
nextMove = (nextMove == WHT)? BLK : WHT; //whose move next
displayBoard();
}
Serial << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
cBoard* fSquare = rbTree.nodeSearch(from);
cBoard* tSquare = rbTree.nodeSearch(to);
if(fSquare) {
if(fSquare->player == nextMove) {
if(tSquare == NULL || tSquare->player != nextMove) {
// probably a valid move but you could write a lot more
// validation to check route is clear if not knight and
// distance allowed and from and to not the same etc.
if(tSquare) {
rbTree.deleteNode(to);
}
rbTree.insertNode(to, fSquare);
rbTree.deleteNode(from);
} else {
Serial << "Target square invalid\n";
}
} else {
Serial << "Not your move\n";
}
}
}
void setupBoard() {
cBoard wSquare = {WHT, PAWN}, bSquare = {BLK, PAWN};
for(int i = 1; i < 9; i++) {
wSquare.piece = bSquare.piece = PAWN;
rbTree.insertNode(i + 8, &wSquare);
rbTree.insertNode(i + 48, &bSquare);
switch(i) {
case 1:
case 8:
wSquare.piece = bSquare.piece = ROOK;
break;
case 2:
case 7:
wSquare.piece = bSquare.piece = KNIGHT;
break;
case 3:
case 6:
wSquare.piece = bSquare.piece = BISHOP;
break;
case 4:
wSquare.piece = bSquare.piece = QUEEN;
break;
case 5:
wSquare.piece = bSquare.piece = KING;
break;
}
rbTree.insertNode(i, &wSquare);
rbTree.insertNode(i + 56, &bSquare);
}
}
void displayBoard() {
cBoard* square;
for(int i = 0; i < 8; i++) {
for(int j = 1; j < 9; j++) {
square = rbTree.nodeSearch(j + i * 8);
if(square) {
Serial << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece]+32));
}else {
Serial << ' ';
}
}
Serial << '\n';
}
Serial << '\n';
}
Read the chapter in my book C++ Data Structures with immediate download from Amazon