A red-black tree is a kind of binary search tree that is balanced.
Why do we want a binary search tree that is balanced?
A balanced tree guarantees a limit on the height (O (lg n)), which puts a time cap on non-modifying tree operations (min, max, successor, predecessor, search) of O(lg n).
Red-black trees have __________ that is used to maintain the tree's "balance".
an extra bit of information - "red" or "black"
(T/F) All balanced trees guarantee logarithmic height.
True.
In a red-black tree every node is either ____________.
red or black
In a red-black tree the root is ____________.
black
In a red-black tree every leaf is ____________.
NIL and black
In a red-black tree if a node is red then both its children are ____________.
black
In a red-black tree, for each node, all simple paths to its descendant leaves have the ____________.
same number of black nodes (this is why the concept of black height is important)
Look at the illustration of a red-black tree.
What is the height of a node in a tree?
The height is the number of edges in the longest path to a leaf.
What is the black height of a node in a red-black tree?
The black height is the number of black nodes (including T.nil) on the path from x to leaf (not counting x).
Look at the illustration regarding height and black height.
How are the height and black height of a node related?
If a node has height h, its black height must be >= h/2. Why? The fourth property of a red-black tree states that if a node is red then its children must be black. On a path, each red node must be followed by a black node. Therefore at least h/2 of the nodes on the path from the node to a leaf are black.
What can be said about the number of nodes rooted at any node x in a red black tree?
Because a red-black tree is balanced, the number of nodes in a level is a power of 2^level. The number of nodes in a tree rooted at a node x in a red black tree can be expressed as 2 ^ (black height of x) - 1.
What formula expresses the relationship between the height of a red-black tree and the number of nodes (n) in a tree?
h(x) <= 2 lg (n+1)
What method is used to change the shape of a red-black tree?
Rotation - one side gets taller, the other shrinks.
Why is rotation used in a red-black tree?
Rotation is used to maintain red-black tree properties upon insertion. It maintains the inorder ordering of keys, and relative subtree heights stay the same.
Look at the rotation example.
Look at pseudocode for Left-Rotate.
(T/F) Search, Min, Max, Successor, and Predecessor are the same for Red-Black tree as for Binary Search Tree.
True.
(T/F) Insert and Delete are the same for Red-Black tree as they are for Binary Search Tree.
False. A Red-Black has more properties (to maintain a balanced tree) to maintain than a binary search tree. Upon insertion, color must be assigned to the new node and adjustments may need to be made to the tree to ensure that it continues to meet the conditions for a Red-Black tree. Upon deletion, recolorings and positional changes may need to be made to ensure continued compliance with Red-Black Tree conditions.
On insert, what color is the new node initially assigned?
Red. Even though this might violate property 4 (red parent => both children are black), this problem is easier to correct than making initial color black (might violate property 5 (all paths to descendants have same number of black nodes)).
When a node is deleted, does the color of the deleted node have any bearing on any adjustments that may need to be made to the red-black tree?
Yes. If the deleted node was red, we won't have changed any black heights, nor will we have caused there to be two red nodes in a row. But, if the deleted node was black, we could cause there to be two red nodes in a row (violation of property 4), or we could cause there to be problem with black heights. Also, if the root was deleted, one of its children (which must be red), will become the root (which must be black) (property 2).
Generally speaking, how do we insert a new node into a red-black tree?
First, insert the new node as a RED leaf into the red-black tree (just like the insertion into a binary search tree). This MAY cause a red-red violation or a red root violation, which is fixed with a RB-Insert-Fixup procedure.
Look at the pseudocode for RB-Insert.
Look at the pseudocode for RB-Insert-Fixup.
For an insert into a red-black tree, there are three cases involving red-red violations that must be handled if they occur on insert. What are they?
1. If the newly inserted node causes a r-r violation and has a red uncle, recolor above generations - but only until the problem is fixed or another case is encountered (recoloring the whole tree could cause a red root).
2. Black uncle with zig-zag - move problem to a parent and rotate on parent to remove zig-zag.
3. Black uncle without zig-zag - recolor parent to black and grandparent to red, then rotate on grandparent to balance.
*There is an example regarding these cases.*
See examples about the 3 cases of red-red violations and how to resolve them.
See example of red-black tree insertion that progresses through all 3 cases.