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:
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 self-balancing tree that build upon the ideas of binary search trees.
- Red-black tree builds upon both of these two tree structures.
- Red-black 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.
- a type of self-balancing binary search tree,very similar to other self-balancing trees, such as AVL trees.
- adhere to a strict set of rules to maintain a log time complexity and stays balanced.
- 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.
nullleaf node is always considered to be a black node, not red.
- these 4 rules are super strict and very easy to break.
- A chain of three nodes cannot possibly every be a valid red-black tree.
The trickiest time to follow the rules of red-black trees is when we’re growing or shrinking the tree.
A perfectly-balanced red-black tree is great, but most data structures tend to have elements and data inserted and removed from them. When it comes to red-black trees, this can be a little daunting at first.
- 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 red-black 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
3to be red, instead of black, we don’t violate any of our four red-black tree rules.
- recoloring nodes is one well-used technique for handling insertions and deletions into a red-black 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.
- Rotations tend to move around and restructure the subtrees of a larger red-black tree, which can also be helpful in preventing any rule violations.
- left-rotation : left-rotating on the root node,
4, so that it’s right child,
11, becomes the new parent ; the subtree of
9-5-10moved from the right subtree to the left.
- right-rotation : right-rotate on the new parent node,
11, and shift it down so that it once again becomes the right child of
11; The same subtree of
9-5-10moved from the left subtree back to the right.
- 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 node
21to 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.
right-rotate the root node, and shift
21down to become the right child of
recolor our original parent node of the newly-inserted node (which is now the right child),
21, and the root node,
8. If we recolor
21, our root node is back to being black, and our two child nodes are both red.
what about inserting elements into a much larger red-black tree?
- recoloring the parent nodes of our newly-inserted node,
10. This at least solves the problem of rule three being broken!
- can’t recolor
16to 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
16to the right, we’ve effectively pushed down nodes
- two consecutive red nodes that are still breaking rule three:
- left-rotating node
16and making it the new root node. perform a left-rotation on nodes
10so 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).
- Compared to AVL trees, red-black trees are less-perfectly balanced.
- generally need fewer rotations during insertion/deletion with a red-black tree, which makes red-black trees superior for growing or shrinking a free, but less efficient for searching compared to AVL trees.
- The best example of a red-black 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 red-black trees under the hood!
- The duality二元性 of color in red-black 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 red-black 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.
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 object-oriented 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.
- multimap 不可使用  做 insertion,要用内置类型pair<key,vale> ，因为key是可能重复的。
- 可以直接用，c[i] = string(buf);。i是不重复的。