本文是阅读《Painting Nodes Black With RedBlack Trees》的读书笔记，文章来自Vaidehi Joshi在medium上发布baseCS系列，该栏目用可爱的漫画来生动地解释计算机基础、数据结构、算法、理论在实践中的应用。
Intro
Different approaches to solving similar problems.
We depend on as programmers daily are actually built upon more naive solutions that were initially invented by someone else:
 Merge sort was derived as early as 1945.
 bubble sort and the earliest iterations of insertion sort, were invented in 1956.
 timsort: a hybrid of both insertion and merge sort , in 2002.
It is wise to lean on solutions that have already been created by others and build upon them to create our own.
 AVL trees, a type of selfbalancing tree that build upon the ideas of binary search trees.
 Redblack tree builds upon both of these two tree structures.
A very disciplined tree
 Redblack trees were invented in 1978, by two researchers named Leonidas J. Guibas and Robert Sedgewick, at Xerox PARC, a research and development company based in Palo Alto, California.
Definition
 a type of selfbalancing binary search tree,very similar to other selfbalancing trees, such as AVL trees.
 adhere to a strict set of rules to maintain a log time complexity and stays balanced.
Rules
 Every single node in the tree must be either red or black.
 The root node of the tree must always be black.
 Two red nodes can never appear consecutively, one after another; a red node must always be preceded by a black node (it must have a black parent node), and a red node must always have black children nodes.
 Every branch path — the path from a root node to an empty (
null
) leaf node — must pass through the exact same number of black nodes. A branch path from the root to an empty leaf node is also known as an unsuccessful search path, since it represents the path we would take if we were to search for a node that didn’t exist within the tree.
Example
 a
null
leaf node is always considered to be a black node, not red.
 these 4 rules are super strict and very easy to break.
Proof
 A chain of three nodes cannot possibly every be a valid redblack tree.
Following the rules of red
The trickiest time to follow the rules of redblack trees is when we’re growing or shrinking the tree.
A perfectlybalanced redblack tree is great, but most data structures tend to have elements and data inserted and removed from them. When it comes to redblack trees, this can be a little daunting at first.
inserting a node
strategy 1 : red
 Inserting a node and immediately coloring it red makes it much easier to identify and subsequently fix any violations.
The first step is basically ignoring the redblack rules, and initially just figuring out where the node would go according to the rules of a normal binary search tree.
At first, when we insert this node, we’ll break rule four.Instead, if we recolor our inserted node with a value of
3
to be red, instead of black, we don’t violate any of our four redblack tree rules.
insert another node
strategy 2 : recoloring
 recoloring nodes is one wellused technique for handling insertions and deletions into a redblack tree.
locate the position for the node and recolor it to be red.
However, we could also recolor the black parent node,
4
, to be red instead of black.
strategy 3 : rotations
 Rotations tend to move around and restructure the subtrees of a larger redblack tree, which can also be helpful in preventing any rule violations.
 leftrotation : leftrotating on the root node,
4
, so that it’s right child,11
, becomes the new parent ; the subtree of9510
moved from the right subtree to the left.  rightrotation : rightrotate on the new parent node,
11
, and shift it down so that it once again becomes the right child of11
; The same subtree of9510
moved from the left subtree back to the right.
Example 1
Remember
 it’s easiest to start off by always inserting a red node, and then recoloring and rotation as necessary, afterwards.
start with a single root node of
21
, which will be red. recolor node21
to be black.insert a node with a value of
8
, as the left child of the root. We can insert it as a red node.insert a node with a value of
3
. rotate the grandparent node (the root) and then recolor.rightrotate the root node, and shift
21
down to become the right child of8
.recolor our original parent node of the newlyinserted node (which is now the right child),
21
, and the root node,8
. If we recolor8
and21
, our root node is back to being black, and our two child nodes are both red.
The benefits of painting it black
what about inserting elements into a much larger redblack tree?
Complicated Example 2
 recoloring the parent nodes of our newlyinserted node,
10
. This at least solves the problem of rule three being broken!  can’t recolor
16
to be black, because if we did that, we’d be violating rule four.  there are no parent nodes left to recolor (except for the root node, which we don’t want to make red!), we can now lean on rotations to help us out.
 rotating node
16
to the right, we’ve effectively pushed down nodes21
,27
, and29
.注意这里将16的右子树移到21的左边了!  two consecutive red nodes that are still breaking rule three:
16
and21
.  leftrotating node
16
and making it the new root node. perform a leftrotation on nodes9
and10
so that they both are on the left subtree rather than the right subtree.
 recolor our root (as well as it’s left child, to make sure that we don’t violate rule 4).
Time Complexity and Space Complexity
 Compared to AVL trees, redblack trees are lessperfectly balanced.
 generally need fewer rotations during insertion/deletion with a redblack tree, which makes redblack trees superior for growing or shrinking a free, but less efficient for searching compared to AVL trees.
 The best example of a redblack trees in use today is the Linux kernel’s Completely Fair Scheduler (CFS), which was introduced as recently as 2007. This scheduler handles resource allocation for executing process from within the CPU, and actually uses redblack trees under the hood!
 The duality二元性 of color in redblack trees is a key part to all four of its rules, and an important part of keeping the tree balanced.
 As we already know, each node in a redblack tree must be either red or black. This is effectively an added piece of information that every single node must keep track of; at first, this might seem silly, because we’re tracking yet another piece of information in each node, which takes up space!
 However, tracking the color of a node requires only 1 bit of storage.
 1 bit is a single binary digit , is a super minuscule amount of space to store either the color red or black.
Story
Robert Sedgewick, who is now a professor at Princeton (and teaches an online algorithms course!), explained this story himself:
A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC which was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, ethernet and objectoriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that’s why we picked the color red to distinguish red links, the types of links, in three nodes.
C++的有序关联式容器底部支持
我容易弄混map和unordered_map的底部支持。学了红黑树之后，了解到rbt具有有序的特性，而unordered_map是一种无序的关联式容器，所以unordered_map是用hash table实现的！！！C++11以前GUN版本的unordered_map是叫做hash_map。
以下内容来自侯捷老师的《STL标准库与泛型编程》课程中的测试代码，演示了各种有序关联式容器的使用效果。
multiset
1 

 最后清空容器
multimap
1 

 multimap 不可使用 [] 做 insertion,要用内置类型pair<key,vale> ，因为key是可能重复的。
set
1 

 这里set的实际大小是32768，因为每个key是不重复的，他的类型是long,4个字节，范围是0~32767,2^151.
 用容器对应的find()方法比std全局的find()方法要快很多，百万级数据是20ms的差别！
map
1 

 构建百万级数据容器的时候花了22秒，但是在搜索的时候很快！说明rbt很适合搜索！！
 而由于rbt比avl的平衡性差一些，所以在搜索方面avl更快，而rbt在建树速度上优于avl！！
 可以直接用[]，c[i] = string(buf);。i是不重复的。
Resources
 Coursera Lecture 45 — RedBlack BSTs, Robert Sedgewick
 Generic RedBlack Tree, Dr. Richard Wiener
 RedBlack Trees, Professor Jim Skrentny
 Red/Black Tree Visualization, Professor David Galles
 RedBlack Tree Introduction, GeeksforGeeks