Red-black tree is most popular self-balancing binary search tree algorithm. First introduced by [Leonidas J. Guibas](https://en.wikipedia.org/wiki/Leonidas_J._Guibas) and [Robert Sedgewick](https://en.wikipedia.org/wiki/Robert_Sedgewick_(computer_scientist)) in the 1978 paper "A Dichromatic Framework for Balanced Trees". Their work inspired by previous work by [Rudolf Bayer](https://en.wikipedia.org/wiki/Rudolf_Bayer) at 1972. The most recent variant of red-black tree is Left-Lining Red-Black (LLRB) tree invented by [Robert Sedgewick](https://en.wikipedia.org/wiki/Robert_Sedgewick_(computer_scientist)) in the 2008 paper ["Left-leaning Red-Black Trees"](https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf).

Basically, red-black tree is improved version of [2-3 tree](https://en.wikipedia.org/wiki/2%E2%80%933_tree) by represent 2-3 tree as binary search tree. Red-black tree use *red link* to bind together 2-nodes to represent 3-nodes, then connecting each childs to its parent using *black link*. Consider an image below:


The first part of image (above) is 3-nodes representation in 2-3 tree, while the second part of image (below) is 2-nodes representation using red and black links.

Since red-black tree break down 3-nodes into 2-nodes representation, the find operation similar to find operation in regular binary search tree.

Flipping color is key concept in red-black tree in order to maintain balance of tree while rotation executed when insertion and deletion occured. Consider three images below with their implementation in Java:




Notice that when subtree is balanced, parent's colors flipped from red to black.

Just keep in mind that:

* When insertion caused tree has incomplete leaves, then each unbalanced tree has red link.

* When insertion caused tree has complete leaves, then all red links dismissed.


An interactive animation of left-leaning red-black tree can be found at [here](http://inst.eecs.berkeley.edu/~cs61b/fa17/materials/demos/ll-red-black-demo.html)

* search: `2 lg N`

* insert: `2 lg N`

* delete: `2 lg N`

* search: `~ 1.00 lg N`

* insert: `~ 1.00 lg N`

* delete: `~ 1.00 lg N`

MySQL used Red-Black tree to store index keys in memory and key value into B-Tree. When memory reach its limits, MySQL writes all keys to disk.

* [Algorithm 4 edition](https://algs4.cs.princeton.edu/33balanced/)

* [Algorithm course slides](https://drive.google.com/file/d/1XC5qTc-9XdR2waDoNnxD-FH66ocFX2DO/view)

* [Bulk insert MySQL](https://dev.mysql.com/doc/internals/en/bulk-insert.html)

* [The Physical Structure of an InnoDB Index](https://dev.mysql.com/doc/refman/8.0/en/innodb-physical-structure.html)

* [wikipedia](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)

const STRING_ENCODING_LENGTH = 8;

const STRING_SEGMENT = 58;

const STRING_COMBINATION = STRING_SEGMENT ** STRING_ENCODING_LENGTH;

export default class RedBlackNode {

/**

constructor(key = null, value = null, color = null, size = 1) {

this.left = null;

this.right = null;

if (typeof key === 'string') {

if (key.length > STRING_ENCODING_LENGTH) {

throw new Error('String type key exceed STRING_ENCODING_LENGTH');

}

}

this.key = key;

this.value = value;

this.color = color; // Color of parent link

this.size = size; // Size of subtree

}

decodeStrKey(key) {

if (typeof key !== 'string') {

throw new Error('Input should be string');

}

let k = 0;

if (key.length > 1) {

k = [...key.slice(1)]

.map(char => char.charCodeAt(0) - 64)

.reduce((current, previous) => current + previous);

}

k += (key.charCodeAt(0) - 64) * STRING_COMBINATION;

return k;

}

/**

compareTo(node) {

if (typeof this.key === 'number' && typeof node.key === 'number') {

if (this.key > node.key) return 1;

if (this.key < node.key) return -1;

return 0;

}

if (typeof this.key === 'string' && typeof node.key === 'string') {

// Compare based on sum of char codes

const key1 = this.decodeStrKey(this.key);

const key2 = this.decodeStrKey(node.key);

if (key1 > key2) return 1;

if (key1 < key2) return -1;

return 0;

}

const t1 = typeof this.key;

const t2 = typeof node.key;

throw new Error(`Not consistent comparation type: ${t1} versus ${t2}`);

}