Transcript Red-Black tree

CO4301 – Advanced Games
Development
Week 5
Red-Black Trees
Gareth Bellaby
1
Red-Black trees
2
Importance
•
•
Used in partitioning
Z-order
3
Balanced tree
•
•
•
•
•
•
A balanced tree is one such that for any two
leaves the difference of the depth is at most 1.
This is a height balanced tree.
There is a also a weight balanced tree.
The height of a balanced tree is O(log n)
This means therefore
complexity is O(log n)
that
a worst-case
This the best possible form that a binary
search tree could take.
4
Balanced tree
•
•
•
If the tree becomes unbalanced then its
efficiency will decrease.
Q: what's the worst it can become? Form?
Worst-case complexity?
Notice that it could only take 1 insertion for the
tree to become unbalanced.
5
Balanced tree
•
•
•
A balanced tree is an efficient implementation
for a list.
Priority queues (talked about these last week)
As we shall see it can also be used for sets,
maps, multimaps and associative arrays.
6
Self-balancing tree
•
•
•
•
•
Self-balancing tree is one that keeps its height,
There are a number of data structures which
implement a self-balancing tree.
2-3 trees
Splay trees
SVL tree
7
Red-Black tree
•
•
Not perfect, but a reasonable approximation
which means it works near optimally.
1978 paper, "A Dichromatic Framework for
Balanced Trees", Leonidas J. Guibas and
Robert Sedgewick
8
Red-Black tree
•
•
•
•
Start with binary tree
Each node is given an extra binary tracking
value.
The metaphor used is painting. It is called a
red-black tree because a node is painted red
or black.
Colouring simplifies the data structure. Every
node is coloured.
9
Red-Black tree
•
•
•
•
•
•
Binary tree.
Root is black
Each leaf is black.
Children of a red node are black.
Every path from a node to all of its descendent
leaf nodes contain the same number of black
nodes. Or alternatively, all of the leaves have
the same black depth (count of black nodes up
to the root).
Leaf does not contain data.
10
Red-Black tree examples
11
Red-Black tree
•
•
•
What these rules do is enforce the property
that any path from the root to a leaf is no more
than twice as long as any other.
The tree is therefore efficient.
The tree is roughly height balanced.
12
Red-Black tree
•
•
•
•
By convention, Null (or Nil) leaves are black.
Some use the convention that you don't need
to draw the Null leaves.
A red-black tree has height O(log n)
Search is the same as for a binary search tree.
13
Red-Black tree example
14
Implementation observations
•
•
Note that the leaf nodes do not have to be
explicitly stored. The link to the child node
could include the information that it is leaf.
Extra data for each node is only binary. A
common approach is se a bit to store the
value, thereby incurring little or no extra
memory. However, remember word size and
memory. Note this works both ways: a single
bit could mean the incursion of an extra cost.
However, a node may well have excess space
because it doesn't take up a full word size and
so no cost to store the extra bit.
15
Implementation observations
•
Also note that you could use a single node for
all of the child nodes. Since by definition the
child is a leaf, it doesn't matter if all of the
references to a leaf actually point to the same
node.
16
BST
•
•
•
Add the node as any binary search tree
insertion
BST = binary search tree.
For every node n
• All keys in n's left subtree are less than the
key in n, and
• All keys in n's right subtree are greater than
•
the key in n.
(There are other ways to express this !)
17
BST Insertion
•
•
•
•
Insert into BST Tree
New nodes are always inserted as leaves.
Use binary search to find a node whereby
inserting the new node does not break the BST
property.
If root empty, then make new node the root
and quit.
18
BST Insertion algorithm
•
•
•
•
New node = n
current = root
If (key of n) < (key of current)
• If current has a left child, search left
• Else add n as a left child to current
If (key of n) > (key of current)
• If current has a right child, search right
• Else add n as a right child to current
19
Red-Black tree Insertion
•
•
•
•
Objective is to add a node whilst maintaining
the red-black properties of the tree.
Need to change the structure of the tree. This
is done by "rotation"
Rotation will preserve the binary search tree
property.
Can do the rotation on different nodes within
the tree, the nodes can have subtrees.
20
Rotation
•
Left rotation on x
•
•
Inverse
operation
Right rotation on y
21
Red-Black tree Insertion
•
Objective is to add a node whilst maintaining
the red-black properties of the tree.
• Perform a BST insertion.
• Colour the inserted node red (unless it is the
root, in which case colour it black)
22
Red-Black tree Insertion
•
•
There are two properties which can be
violated. Firstly, the property "Root is black".
This is dealt with trivially by adding the proviso
that if it is the root node then colour it black
instead and quit.
The only other possible red-black property
which can be violated is the one "Children of a
red node are black.“ (Alternatively expressed
as “a red node cannot have a red child”).
23
Red-Black tree Insertion
•
•
Check colour of the parent.
If parent is black then the insertion has not
changed the property of the tree and so
everything is OK. Quit.
24
Red-Black tree Insertion
•
If parent is red this breaks the property
"Children of a red node are black."
25
Red-Black tree Insertion
•
•
•
•
Call the inserted node N.
Call the parent P.
Grandparent: parent of the parent. Call it G.
Uncle: the other child of the grandparent. Call it
U.
26
Insertion Case 1
•
•
•
•
A number of different cases:
Case 1:
If the uncle of N is red.
Recolour the node's parent, grandparent and
uncle. Continue recursively with rest of tree (to
be explicit: make uncle and parent black, and
make node and grandparent red.)
• Carry on up the tree. Make the grandfather
the new node N, i.e. moving up the tree by
two levels
27
Insertion Case 1
•
•
•
Case 1:
The uncle of N is red.
Recolour the node's parent, grandparent and
uncle. Continue recursively with rest of tree.
=>
28
Insertion Case 2
•
•
•
•
•
The other two cases are when the uncle of N is
black. Either N is the left child or N is the right
child. We want to make N the left child so let’s
start with the case where N is a right child:
Case 2: the uncle of N is black and N is a right
child.
Do a left rotation on P to make N a right child.
Re-label N and P.
Now falls into case 3.
29
Insertion Case 2
•
•
Case 2: the uncle of N is black and N is a right
child.
Do a left rotation on P.
30
Insertion Case 2
•
Relabel N and P.
•
Now falls into case 3.
31
Insertion Case 3
• Case 3: the uncle of N is black and
N is a left child.
• Do a right rotation on G.
• Swap colours of P and G.
32
Insertion Case 3
• Do a right rotation on G.
G
P
A
U
C
N
P
N
A
G
B
C
U
B
33
Insertion Case 3
• Swap colours of P and G.
34
Red-Black tree Insertion
•
•
•
•
Nice visualisation:
https://www.cs.usfca.edu/~galles/visualization/
RedBlack.html
The summary on Wikipedia is quite good, but
note that my number of the cases is different.
See also the references I’ve given
35
References
•
•
•
Leonidas J. Guibas and Robert Sedgewick, "A
Dichromatic Framework for Balanced Trees“
T Cormen,, C Leiserson, R Rivest, C Stein,
Introduction to Algorithms
Frank M. Carrano, Timothy Henry, Data
Abstraction & Problem Solving with C++: Walls
and Mirrors Paperback
36
Next Few Weeks
•
Patterns
•
15-20 minute presentation on a pattern
•
Game Programming Patterns
•
Robert Nystrom, Game Programming Patterns
37
Patters References
•
•
•
•
Robert Nystrom, Game Programming Patterns
http://gameprogrammingpatterns.com/
Erich Gamma, Richard Helm, Ralph Johnson,
John Vlissides (the GangOfFour), Design
Patterns: Elements of Reusable ObjectOriented Software
Note that Chapter 3: Creational Patterns, is
about building a maze
38
Next Week
•
•
•
•
http://www.gamasutra.com/view/feature/13264
9/the_case_for_game_design_patterns.php
http://www.gamasutra.com/blogs/MichaelHane
y/20110920/90250/Design_Patterns_in_Game
_Programming.php
Julian
Gold,
Development
Object-Oriented
Game
Chapter 2 of Bruce Sutherland, C++ Game
Development Primer
39
Topics
•
•
•
•
•
•
•
•
Abstract Factory
Builder:
Factory Method
Prototype
Observer
Chain of responsibility
State
Composite
40
Topics
•
•
•
•
•
•
•
•
Adapter
Facade
Flyweight
Proxy
Command
Mediator
Strategy
Template method
41