Transcript Red-black trees

Today’s special: 4 for 1
Quiz3!
Midterm!
Assignment2!
(most) Quiz4!
Balanced trees:
Red-Black Trees
Definitions
Insertion
In a nutshell
Definition: an extended Node
Before, all our nodes were born equals.
In a red-black tree, a node is either red or black.
For some algorithms, it is easier to have a pointer to the parent.
public class RBNode extends Node{
private Node parent;
private boolean color;
// true for black, false for red
right
parent
public RBNode(int key, Object data) {
super(key, data);
parent = null;
color = true;
}
left
parent
}
Balanced trees: Red-black trees
Definition: Red-Black Tree
• Each node must have exactly two children. For each child
that is lacking, you create a fake black one.
10
13
5
needs two fake
children →
7
13
6
← needs two fake children
← needs one fake child
9
← needs two fake children
Balanced trees: Red-black trees
Definition: Red-Black Tree
• Each node must have exactly two children. For each child
that is lacking, you create a fake black one.
10
13
5
In practice,
don’t bother
drawing them.
7
13
6
Think of those as
gostly nodes: they
are not really
there…
9
Balanced trees: Red-black trees
Definition: Red-Black Tree
• Each node must have exactly two children. For each child
that is lacking, you create a fake black one.
• The root is black.
• Every path from a node to a leaf contains the same number
of black nodes.
• If a node is red then both its children must be black.
Balanced trees: Red-black trees
Example
The root is black.
The children of red
nodes are both black.
Balanced trees: Red-black trees
Example
The root is black.
The children of red
nodes are both black.
Balanced trees: Red-black trees
Algorithm: Insertion
A red-black tree is a particular binary search tree, so create a
new node as red and insert it.
5
7
9
7
Violation!
What property may be violated? The children of a red node
must be black.
(similarly to an AVL: you insert the node, that may screw up a few
properties, so you try to fix them after)
Balanced trees: Red-black trees
Algorithm: Insertion
There are different situations, and fixing them
follows a very scientific and rigorous process.
Balanced trees: Red-black trees
Algorithm: Insertion
We have detected a need for balance when z is red and his parent too.
• If z has a red uncle: colour the parent and uncle black, and grandparent red.
z
Balanced trees: Red-black trees
Algorithm: Insertion
We have detected a need for balance when z is red and his parent too.
• If z has a red uncle: colour the parent and uncle black, and grandparent red.
• If z is a left child and has a black uncle: colour the parent black and the
grandparent red, then rotateRight(z.parent.parent)
Balanced trees: Red-black trees
Algorithm: Insertion
We have detected a need for balance when z is red and his parent too.
• If z has a red uncle: colour the parent and uncle black, and grandparent red.
• If z is a right
childand
andhas
hasa ablack
blackuncle:
uncle,colour
then rotateLeft(z.parent)
left child
the parent black andand
the
grandparent red, then rotateRight(z.parent.parent)
Balanced trees: Red-black trees
Algorithm: Insertion
Let’s insert 4, 7, 12, 15, 3 and 5.
4
7
12
Double red violation!
It also shows it’s
unbalanced…
Balanced trees: Red-black trees
Algorithm: Insertion
Let’s insert 4, 7, 12, 15, 3 and 5.
7
What should we do?
Nothing, no
double red.
3
4
12
5
15
Double red violation.
We can’t have a better
balance, and there is a
red uncle…
Balanced trees: Red-black trees
Algorithm: Insertion
To practice more: http://gauss.ececs.uc.edu/RedBlack/redblack.html
7
4
9
3
5
6
2
1
Balanced trees: Red-black trees
In a nutshell:
What to optimize?
Which operation matters?
We have seen how to use three primitive structures: arrays, simple
pointers (as in a LinkedList) and trees.
If we want to optimize the access, which primitive would you choose?
An array, because access is in O(1).
If we want to optimize the insertion, which primitive would you choose?
Pointers with a shortcut to the tail.
Inserting at the end will be O(1).
What about we want to optimize insertion and access?
Balanced trees: Red-black trees
Which operation matters?
You can’t have O(1) for both.
But with a balanced tree you
get O(log n).
If you want to optimize one
operation, go for arrays or simple
pointers. Beyond, use a tree.
What about we want to optimize insertion and access?
Balanced trees: Red-black trees
A bit of practice
1a) Write a method findAllElements that returns the content of a binary
search tree as a LinkedList L.
1b) Let say that we delete the tree and we add all the elements from L to
the tree again, from first to last. How can you ensure that we will get the
same tree back?
2a) Write a method showPath(int key1, int key2) that will show the keys
on the path from key1 to key2. Assume both keys exist.
2b) Write showPathReverse(int key1, int key2) that will show the keys in
the other order (from key2 to key1).
2c) Write showPathReverse(int key1, int key2) without recursive calls.
Balanced trees: Red-black trees