Chapter 12 GRAPHS
1,Mathematical Background
2,Computer Representation
3,Graph Traversal
4,Topological Sorting
5,A Greedy Algorithm,Shortest
Paths6,Minimal Spanning Trees
7,Graphs as Data Structures
12.1 Mathematical Background
Definitions and Examples
1,A graph G consists of a set V,whose members are
called the vertices of G,together with a set E of pairs
of distinct vertices from V,
2,The pairs in E are called the edges of G.
3,If e = (v,w) is an edge with vertices v and w,then v
and w are said to lie on e,and e is said to be incident
with v and w.
4,If the pairs are unordered,G is called an undirected
graph.
5,If the pairs are ordered,G is called a directed graph,
The term directed graph is often shortened to
digraph,and the unqualified term graph usually
means undirected graph.
依附于 关联
6,Two vertices in an undirected graph are called
adjacent if there is an edge from the first to the
second.
7,A path is a sequence of distinct vertices,each
adjacent to the next.
8,A cycle is a path containing at least three vertices
such that the last vertex on the path is adjacent to
the first.
9,A graph is called connected if there is a path from
any vertex to any other vertex.
10,A free tree is defined as a connected undirected
graph with no cycles.
11,In a directed graph a path or a cycle means always
moving in the direction indicated by the arrows,
Such a path (cycle) is called a directed path (cycle).
12.A directed graph is called strongly connected if
there is a directed path from any vertex to any other
vertex,If we suppress the direction of the edges and
the resulting undirected graph is connected,we call
the directed graph weakly connected.
13.The valence of a vertex is the number of edges on
which it lies,hence also the number of vertices
adjacent to it.
Examples of Graphs
Various kinds of undirected graphs
Examples of directed graphs
12.2 Computer Representation
Set Implementations of Digraphs pg.573
Definition A digraph G consists of a set V,called
the vertices of G,and,for all v?V,a subset Av of V,
called the set of vertices adjacent to v.
directed graph
Digraph as a bit-string set:
template <int max_size>
class Digraph
{ int count;
Set<max_size> neighbors[max_size];
};
number of vertices
at most max_sizeSet as a bit string,pg.573
template <int max_set>
struct Set
{ bool is_element[max_set]; };
Digraph as an adjacency table,pg.574
template <int max_size>
class Digraph
{ int count;
bool adjacency[max_size][max_size];
};
Adjacency
matrix
List Implementation of Digraphs
typedef int Vertex;
template <int max_size>
class Digraph
{ int count;
List<Vertex> neighbors[max_size];
};
Array
Of List
class Edge;
class Vertex
{ Edge *first_edge;
Vertex *next_vertex;
};
forward declarationstart of the
adjacency listnext vertex on the linked list
class Edge
{ Vertex *end_point;
Edge *next_edge;
};
vertex to which
the edge pointsnext_edge on the adjacency list
class Digraph
{ Vertex *first_vertex; };
header for the
list of vertices
12.3 Graph Traversal pg.575
1,Methods pg.575
? Depth-first traversal of a graph
is roughly analogous to
preorder traversal of an ordered
tree,Suppose that the traversal
has just visited a vertex v,and
let w1,w2,… wk be the vertices
adjacent to v,Then we shall next
visit w1 and keep w2,… wk
waiting,After visiting w1,we
traverse all the vertices to which
it is adjacent before returning to
traverse w2,… wk,
? Breadth-first traversal of a
graph is roughly analogous
to level-by-level traversal of
an ordered tree,If the
traversal has just visited a
vertex v,then it next visits
all the vertices adjacent to v,
putting the vertices adjacent
to these in a waiting list to
be traversed after all
vertices adjacent to v have
been visited.
2,Depth-First Algorithm pg.577-578
template <int max_size> void Digraph<max_size>::
depth_first(void (*visit)(Vertex &)) const
/* Post,The function *visit has been performed at each
vertex of the Digraph in depth-first order.
Uses,Method traverse to produce the recursive
depth-first order,*/
{ bool visited[max_size];
Vertex v;
for (all v in G) visited[v] = false;
for (all v in G)
if (!visited[v])traverse(v,visited,visit);
}
The recursion is performed in an auxiliary function traverse.
template <int max_size> void Digraph<max_size>::
traverse ( Vertex &v,bool visited[],
void (*visit)(Vertex &) ) const
/* Pre,v is a vertex of the Digraph,
Post,The depth-first traversal,using function*visit,
has been completed for v and for all vertices
that can be reached from v,
Uses,traverse recursively,*/
{ Vertex w;
visited[v] = true;
(*visit)(v);
for(all w adjacent to v)
if(!visited[w])traverse(w,visited,visit);
}
3,Breadth-First Algorithm pg,578
template <int max_size> void Digraph<max_size>::
breadth_first(void (*visit)(Vertex &)) const
{ Queue q; bool visited[max_size]; Vertex v,w,x;
for (all v in G) visited[v] = false;
for (all v in G)
if (!visited[v])
{ q.append(v);
while(!q.empty( ))
{ q.retrieve(w);
if (!visited[w])
{ visited[w] = true; (*visit)(w);
for(all x adjacent to w) q.append(x);
}
q.serve( );
}
}
}
12.4 Topological Sorting pg,579
Let G be a directed graph with no cycles,A
topological order for G is a sequential listing of all
the vertices in G such that,for all vertices v,w ? G,
if there is an edge from v to w,then v precedes w
in the sequential listing.
Directed graph with no directed cycles
Depth-first ordering
Breadth-first ordering
1,Digraph Class,Topological Sort
typedef int Vertex;
template <int graph_size> class Digraph
{ public:
Digraph( );
void read( );
void write( );
// methods to do a topological sort
void depth_sort(List<Vertex> &topological order);
void breadth_sort(List<Vertex> &topological order);
private:
int count;
List <Vertex> neighbors[graph_size];
void recursive depth_sort(Vertex v,bool visited[],
List<Vertex> &topological_order);
}
2,Depth-First Algorithm
template <int graph_size> void Digraph<graph_size>,:
depth sort(List<Vertex> &topological_order)
/* Post,The vertices of the Digraph are placed into List
topological_order with a depth-first traversal of
those vertices that do not belong to a cycle.
Uses,Methods of class List,and function recursive
depth sort to perform depth-first traversal,*/
{ bool visited[graph_size];
Vertex v;
for (v=0; v<count; v++) visited[v]=false;
topological_order.clear( );
for (v=0; v<count; v++)
if (!visited[v])
recursive_depth_sort(v,visited,topological_order);
}
Add v and its successors
into topological_order
template <int graph_size> void Digraph<graph_size>,:
Recursive_depth_sort ( Vertex v,bool *visited,
List<Vertex> &topological_order )
/* Pre,Vertex v of the Digraph does not belong to the
partially completed List topological order,
Post,All the successors of v and finally v itself are
added to topological order with a depth-first search,*/
{ visited[v] = true;
int degree = neighbors[v].size( );
for (int i=0; i<degree; i++)
{ Vertex w; neighbors[v].retrieve(i,w);
if(!visited[w])
recursive_depth_sort(w,visited,topological_order);
}
topological order.insert(0,v);
}
3,Breadth-First Algorithm
template <int graph size> void Digraph<graph size>,:
breadth_sort(List<Vertex> &topological_order)
{ topological_order.clear( );
Vertex v,w;
int predecessor_count[graph size];
for(v=0; v<count; v++) predecessor_count[v] = 0;
for(v=0; v<count; v++)
for(int i=0; i<neighbors[v].size( ); i++)
{ neighbors[v].retrieve(i,w);
predecessor_count[w]++;
}
Queue ready_to_process;
for(v=0; v<count; v++)
if(predecessor_count[v]==0)
ready_to_process.append(v);
Loop over
all edges v-w.
while(!ready_to_process.empty( ))
{ ready_to_process.retrieve(v);
topological_order.insert(topological_order.size( ),v);
for(int j=0; j<neighbors[v].size( ); j++)
{ neighbors[v].retrieve(j,w);
predecessor_count[w]--;
if( predecessor_count[w]==0 )
ready_to_process.append(w);
}
ready_to_process.serve( );
}
}
Traverse
successors of v.
12.5 A Greedy Algorithm,Shortest Paths
1,The problem of shortest paths,pg,583
Given a directed graph in which each edge has a
nonnegative weight or cost,find a path of least
total weight from a given vertex,called the source,
to every other vertex in the graph.
We keep a set S of vertices whose closest
distances to the source,vertex 0,are known
and add one vertex to S at each stage,We
maintain a table distance that gives,for each
vertex v,the distance from 0 to v along a path
all of whose vertices are in S,except possibly
the last one,To determine what vertex to add to
S at each step,we apply the greedy criterion of
choosing the vertex v with the smallest distance
recorded in the table distance,such that v is not
already in distance.
2,Method,pg,584
Finding a Shortest Path
? Choose the vertex v with the smallest distance
recorded in the table distance,such that v is not
already in distance,
? Prove that the distance recorded in distance
really is the length of the shortest path from source
to v,For suppose that there were a shorter path
from source to v,such as shown below.
This path first leaves S to go to some vertex x,
then goes on to v (possibly even reentering S
along the way),But if this path is shorter than
the colored path to v,then its initial segment
from source to x is also shorter,so that the
greedy criterion would have chosen x rather than
v as the next vertex to add to S,since we would
have had distance[x] < distance[v].
See Pg 584,Fig.12.9
? When we add v to S,we think of v as now colored
and also color the shortest path from source to v,
Next,we update the entries of distance by
checking,for each vertex w not in S,whether a
path through v and then directly to w is shorter
than the previously recorded distance to w.
3,Example of Shortest Path
pg.585 fig.12.10
4,Implementation pg.586
template <class Weight,int graph_size>
class Digraph
{ public:
Digraph();
PrintPath();
void set_distances(Vertex source,Weight distance[ ]) ;
protected:
int count;
Weight adjacency[graph_size][graph_size];
};
template <class Weight,int graph_size>
void Digraph<Weight,graph_size>,,
set distances(Vertex source,Weight distance[ ]) const
{ Vertex v,w; bool found[graph_size];
for (v = 0; v < count; v++)
{ found[v] = false;
distance[v] = adjacency[source][v];
}
found[source] = true; distance[source] = 0;
for ( int i = 0; i < count; i++)
{ Weight min = infinity;
for (w = 0; w < count; w++)
if (!found[w])
if (distance[w] < min)
{ v = w; min = distance[w]; }
found[v] = true;
Vertices found
in S
Initialize with
vertex source
alone in the set S.
Add one vertex
v to S on each pass.
for (w = 0; w < count; w++)
if (!found[w])
if (min + adjacency[v][w] < distance[w])
distance[w] = min + adjacency[v][w];
}
}
12.6 Minimal Spanning Trees pg.587
1,The problem, pg,587
? Shortest paths from source 0 to all vertices in a
network.
? If the original network is based on a connected
graph G,then the shortest paths from a particular
source vertex to all other vertices in G form a tree
that links up all the vertices of G.
? A (connected) tree that is build up out of all the
vertices and some of the edges of G is called a
spanning tree of G.
DEFINITION A minimal spanning tree of a connected
network is a spanning tree such that the sum of the weights
of its edges is as small as possible.
2,Method,pg,589
Spanning Trees see pg,589 Fig,12.12
? Prim's Algorithm for Minimal Spanning Trees
? Kruskal's Algorithm for Minimal Spanning Trees
Prim's Algorithm for Minimal Spanning Trees
? Start with a source vertex,Keep a set X of those
vertices whose paths to source in the minimal
spanning tree that we are building have been found,
Keep the set Y of edges that link the vertices in X in
the tree under construction,The vertices in X and
edges in Y make up a small tree that grows to
become our final spanning tree.
? Initially,source is the only vertex in X,and Y is
empty,At each step,we add an additional vertex to
X,This vertex is chosen so that an edge back to X
has as small as possible a weight,This minimal
edge back to X is added to Y.
?For implementation,we shall keep the vertices in
X as the entries of a Boolean array component,We
keep the edges in Y as the edges of a graph that
will grow to give the output tree from our program.
? We maintain an auxiliary table neighbor that gives,
for each vertex v,the vertex of X whose edge to v
has minimal cost,We also maintain a second table
distance that records these minimal costs,If a
vertex v is not joined by an edge to X we shall
record its distance as the value infinity,The table
neighbor is initialized by setting neighbor[v] to
source for all vertices v,and distance is initialized
by setting distance[v] to the weight of the edge
from source to v if it exists and to infinity if not.
?To determine what vertex to add to X at each step,
we choose the vertex v with the smallest value
recorded in the table distance,such that v is not
already in X,After this we must update our tables
to reflect the change that we have made to X,We
do this by checking,for each vertex w not in X,
whether there is an edge linking v and w,and if so,
whether this edge has a weight less than
distance[w],In case there is an edge(v,w) with this
property,we reset neighbor[w] to v and distance[w]
to the weight of the edge.
Example of Prim's Algorithm Pg.591
Function split node,Action
template <class Record,int order>
void B_tree<Record,order>::split_node (
B_node<Record,order> *current,
const Record &extra_entry,
B_node<Record,order> *extra_branch,
int position,
B_node<Record,order> * &right_half,
Record &median )
/* Pre,current points to a node of a B_tree,The node *current is
full,but if there were room,the record extra_entry with its
right-hand pointer extra_branch would belong in *current
at position position,0 ? position < order,
Post,The node*current with extra_entry and pointer
extra_branch at position position are divided into nodes
*current and *right_half separated by a Record median.
*/
Point to
node to be split
new_entry to insertPoint tosubtree on right
of extra_entry
index in node
where extra_entry
goes
Point to new node
for right_half
of entries
med an entry
(in neither half)
{ right_half->data[i-mid] = current->data[i];
right_half->branch[i+1-mid] = current->branch[i+1];
}
current->count = mid;
right_half->count = order-1-mid;
push_in(right_half,extra_entry,extra_branch,position-mid);
}
median = current->data[current->count-1];
right_half->branch[0] = current->branch[current->count];
current->count--;
}
Remove median
from left half
has more than the minimum number of entries,then
one of them can be moved into the parent node,and
the entry from the parent moved into the leaf where the
deletion is occurring.
?If the adjacent leaf has only the minimum number of
entries,then the two leaves and the median entry from
the parent can all be combined as one new leaf,which
will contain no more than the maximum number of
entries allowed.
?If this step leaves the parent node with too few entries,
then the process propagates upward,In the limiting
case,the last entry is removed from the root,and then
the height of the tree decreases.
pg.549 fig.11.14
Public Deletion Method
template <class Record,int order>
Error_code B tree<Record,order>::
remove(const Record &target)
/*Post,If a Record with Key matching that of target belongs
to the B-tree,a code of success is returned and the
corresponding node is removed from the B-tree,
Otherwise,a code of not_present is returned,*/
{ Error_code result;
result = recursive_remove(root,target);
if( root!=NULL && root->count==0 )
{ B_node<Record,order> *old_root = root;
root = root->branch[0]; delete old_root;
}
return result;
}
root is now empty
Recursive Deletion
template <class Record,int order> Error_code
B_tree<Record,order>:,recursive_remove
(B_node<Record,order> *current,const Record &target)
{ Error_code result; int position;
if( current==NULL) return not_present;
if ( search_node(current,target,position)==success ) // 1
{ result = success;
if( current->branch[position]!=NULL ) // ?
{ copy_in_predecessor(current,position);
recursive_remove ( current->branch[position],
current->data[position] );
} // end ?
else remove_data(current,position);
} // end 1
else result=recursive_remove( current->branch[position],
target );
The target is
in the current node
not at a leaf nodeRemove fr m
a leaf node
if( current->branch[position]!=NULL )
if( current->branch[position]->count<(order-1)/2 )
restore(current,position);
return result;
}
Auxiliary Functions
Remove data from a leaf:
template <class Record,int order>
void B_tree<Record,order>::remove_data (
B_node<Record,order> *current,int position )
{ for( int i=position; i< current->count-1; i++ )
current->data[i]=current->data[i+1];
current->count--;
}
Replace data by its immediate predecessor:
template <class Record,int order>
void B_tree < Record,order >::copy_in_predecessor (
B_node<Record,order> *current,int position )
{ B_node<Record,order> *leaf=current->branch[position];
while( leaf->branch[leaf->count]!= NULL )
leaf = leaf->branch[leaf->count];
current->data[position] = leaf->data[leaf->count-1];
}
Restore Minimum Number of Entries
(pg.552 Fig.11.15)
Function to Restore Minimum Node Entries
template <class Record,int order>
void B_tree<Record,order>::
restore(B_node<Record,order> *current,int position)
{ if(position == current->count)
if( current->branch[position-1]->count>(order-1)/2 )
move_right(current,position-1);
else combine(current,position);
else if( position==0 )
if(current->branch[1]->count>(order-1)/2)
move_left(current,1);
else combine(current,1);
else if( current->branch[position-1]->count>(order-1)/2 )
move_right(current,position-1);
else if( current->branch[position+1]->count>(order-1)/2 )
move_left(current,position+1);
else combine(current,position);
}
case,right
most branch
case,left
st rremaining cases:intermediate branches
Function move_left pg553.
template <class Record,int order>
void B_tree<Record,order>,,move_left(
B_node<Record,order> *current,int position)
{ B_node<Record,order>
*left_branch = current->branch[position-1],
*right_branch = current->branch[position];
left_branch->data[left_branch->count] =
current->data[position-1];
left_branch->branch[++left_branch->count] =
right_branch->branch[0];
current->data[position-1] = right_branch->data[0];
right_branch->count--;
Declare pointer
Take entry
from the parentAdd the right-handentry to the parent
for(int i=0; i<right_branch->count; i++)
{ right_branch->data[i] = right_branch->data[i+1];
right_branch->branch[i] = right_branch->branch[i+1];
}
right_branch->branch[right_branch->count] =
right_branch->branch[right_branch->count+1];
}
Move right-hand entries
to fill the hole
Function move_right pg554.
template <class Record,int order>
void B_tree<Record,order>::
move_right(B_node<Record,order> *current,int position)
{B_node<Record,order>
*left_branch=current->branch[position],
*right_branch=current->branch[position+1];
right_branch->branch[right_branch->count+1] =
right_branch->branch[right_branch->count];
for(int i=right_branch->count; i>0; i--)
{ right_branch->data[i] = right_branch->data[i-1];
right_branch->branch[i] = right_branch->branch[i-1];
}
right_branch->count++;
right_branch->data[0] = current->data[position];
right_branch->branch[0] =
left_branch->branch[left_branch->count--];
current->data[position] =
left_branch->data[left_branch->count];
}
Make room
for new entry
Take entry
from parent
Function combine pg554.
template <class Record,int order>
void B_tree<Record,order>::
combine(B_node<Record,order> *current,int position)
{ B_node<Record,order>
*left_branch = current->branch[position-1],
*right_branch = current->branch[position];
left_branch->data[left_branch->count] =
current->data[position-1];
left_branch->branch[++left_branch->count] =
right_branch->branch[0];
for(int i=0; i<right_branch->count; i++)
{ left_branch->data[left_branch->count] =
right_branch->data[i];
left_branch->branch[++left_branch->count] =
right_branch->branch[i+1];
}
current->count--;
for(i=position-1; i<current->count; i++)
{ current->data[i] = current->data[i+1];
current->branch[i+1] = current->branch[i+2];
}
delete right_branch;
}
11.4 Red-Black Trees
1,Introduction
RedBlack
Red-Black Trees as B-Trees of Order 4
See pg.557 Fig,11.16
Red-Black Trees as B-Trees of Order 4
? Start with a B-tree of order 4,so each node contains 1,2,or
3 entries.
? Convert a node with 3 entries into a binary search tree by:
? A node with two entries has two possible conversions:
? A node with one entry remains unchanged.
Red-Black Trees as Binary Search Trees
? A red-black tree is a binary search tree,with links
colored red or black,obtained from a B-tree of
order 4 by the above conversions.
? Searching and traversal of a red-black tree are
exactly the same as for an ordinary binary search
tree.
?Insertion and deletion,require care to maintain
the underlying B-tree structure,
? Each node of a red-black tree is colored with the
same color as the link immediately above it,We
thus need keep only one extra bit of information
for each node to indicate its color.
The Black Condition
Every simple path from the root to an empty
subtree goes through the same number of black
nodes.
? We adopt the convention that the root is colored
black and all empty subtrees (corresponding to
NULL links) are colored black.
?The B-tree requirement that all its empty subtrees
are on the same level becomes:
? To guarantee that no more than three nodes are
connected by red links as one B-tree node,and
that nodes with three entries are a balanced binary
tree,we require:
The Red Condition
If a node is red,then its parent exists and is black.
? We can now define:
Definition A red-black tree is a binary search tree
in which each node has either the color red or
black and that satisfies the black and red
conditions.
Analysis of Red-Black Trees
Theorem 11.2 The height of a red-black tree
containing n nodes is no more than 2lgn.
?Searching a red-black tree with n nodes is O(log n)
in every case.
?The time for insertion is also O(logn)
[ To show this,we first need to devise the
insertion algorithm,]
? An AVL tree,in its worst case,has height about
1.44 lgn and,on average,has an even smaller
height,Hence red-black trees do not achieve as
good a balance as AVL trees.
?Red-black trees are not necessarily slower than
AVL trees,since AVL trees may require many more
rotations to maintain balance than red-black trees
require.
Red-Black Tree Specification
? The red-black tree class is derived from the
binary search tree class.
? We begin by incorporating colors into the nodes
that will make up red-black trees:
enum Color { red,black };
template <class Record>
struct RB_node, public Binary_node<Record>
{ Color color;
RB_node(const Record &new_entry)
{ color=red; data=new_entry; left=right= NULL; }
RB_node( )
{ color = red; left = right = NULL; }
void set_color(Color c)
{ color = c; }
Color get_color( ) const
{ return color; }
};
? Note the inline definitions for the constructors and
other methods of a red-black node.
Modified Node Specification
? To invoke get color and set color via pointers,
we must add virtual functions to the base struct
Binary node.
? The modified node specification is:
template <class Entry> struct Binary_node
{ Entry data;
Binary_node<Entry> *left,*right;
virtual Color get color( ) const { return red; }
virtual void set color(Color c) { }
Binary_node( ) { left = right = NULL; }
Binary_node(const Entry &x)
{data = x; left = right = NULL; }
};
? With this modification,we can reuse all
the methods and functions for manipulating
binary search trees and their nodes.
Red-Black Trees Insertion
?We begin with the standard recursive algorithm
for insertion into a binary search tree,The new
entry will be in a new leaf node.
?The black condition requires that the new node
must be red.
?If the parent of the new red node is black,then
the insertion is finished,but if the parent is red,
then we have introduced a violation of the red
condition into the tree.
?The major work of the insertion algorithm is to
remove a violation of the red condition,and we
shall find several different cases that we shall
need to process separately.
? We postpone this work as long as we can,When
we make a node red,we do not check the conditions
or repair the tree,Instead,we return from the
recursive call with a status indicator showing that
the node just processed is red.
? After this return,we are processing the parent
node.
?If the parent is black,then the conditions for a red-
black tree are satisfied and the process terminates.
?If the parent is red,then we set the status variable
to show two red nodes together,linked as left child
or as right child,Return from the recursive call.
?We are now processing the grandparent node,
Since the root is black and the parent is red,this
grandparent must exist,By the red condition,this
grandparent is black since the parent was red.
? At the recursive level of the grandparent node,we
transform the tree to restore the red-black
conditions,using cases depending on the relative
positions of the grandparent,parent,and child
nodes,See following diagram.
Insertion Method Implementation pg 561.
template <class Record>
class RB_tree,public Search_tree<Record>
{ public:
Error_code insert(const Record & new_entry);
private,
RB_code rb_insert ( Binary_node<Record>*&,
const Record& );
RB_code modify_left ( Binary_node<Record>*&,
RB_code&);
RB_code modify_right ( Binary_node<Record>*&,
RB_code&);
};
Status indicator values,pg 563
enum RB_code{okay,red_node,left_red,right_red,duplicate};
/* okay,The color of the current root(of the subtree) has not
changed; the tree now satisfies the conditions for a red-
black tree.
red_node,The current root has changed from black to red;
modification may or may not be needed to restore the red-
black properties.
right_red,The current root and its right child are now both
red; a color flip or rotation is needed.
left_red,The current root and its left_child are now both
red; a color flip or rotation is needed.
duplicate,The entry being inserted duplicates another entry;
this is an error.
*/
Public Insertion Method pg 563.
template <class Record>
Error_code RB_tree<Record>::
insert(const Record &new_entry)
/* Post,If the key ofnew_entry is already in the RB_tree,
a code of duplicate error is returned,
Otherwise,a code of success is returned and the
Record new_entry is inserted into the tree in such a
way that the properties of an RB-tree have been
preserved.
Uses,Methods of struct RB_node and recursive function
rb_insert, */
{ RB_code status = rb_insert(root,new_entry);
switch (status)
{ case red_node:
root->set_color(black);
case okay,return success;
case duplicate,return duplicate_error;
case right_red:
case left_red:
cout << "WARNING,Program error in
RB_tree::insert" << endl;
return internal_error;
}
} Convert private
RB_code to
public Error_code.
Always split
the root node
to keep it blackSee pg,562 Fig,11.17
Recursive Insertion Function pg 563.
template <class Record>
RB_code RB_tree<Record>::
rb_insert ( Binary_node<Record>* ¤t,
const Record &new_entry)
/* Pre,current is either NULL or points to the first node of a
subtree of an RB_tree
Post,If the key of new_entry is already in the subtree,a
code of duplicate is returned,
Otherwise,the Record new_entry is inserted into the
subtree pointed to by current,
The properties of a red-black tree have been restored,
except possibly at the root current and one of its
children,whose status is given by the output RB_code,
*/
{ RB_code status,child_status;
if( current==NULL )
{ current = new RB_node<Record>(new_entry);
status = red_node;
}
else if( new_entry==current->data ) return duplicate;
else if( new_entry<current->data)
{ child_status = rb_insert(current->left,new_entry);
status = modify_left(current,child_status);
}
else { child_status = rb_insert(current->right,new_entry);
status = modify_right(current,child_status);
}
return status;
}
Checking the Status,Left Child pg 563.
template <class Record>
RB_code RB_tree<Record>::
modify_left ( Binary_node<Record>* ¤t,
RB_code &child_status)
/* Pre,An insertion has been made in the left_subtree of
*current that has returned the value of child_status
for this subtree.
Post,Any color change or rotation needed for the tree
rooted at current has been made,and a status code
is returned.
Uses,Methods of struct RB_node,with rotate_right,
double_rotate_right,and flip_color,*/
{ RB_code status = okay;
Binary_node<Record> *aunt = current->right;
Color aunt_color = black;
if(aunt != NULL) aunt_color = aunt->get_color( );
switch (child_status)
{ case okay,break;
case red_node:
if(current->get_color()==red) status = left_red;
else status = okay;
break;
case left_red:
if( aunt_color==black ) status = rotate_right(current);
else status = flip_color(current);
break;
No action needed,
as tree is already OKcurrent is black,left is red,so OK
case right_red:
if( aunt_color==black )
status = double rotate_right(current);
else status = flip_color(current);
break;
}
return status;
}
Red-Black Trees
Insert 15 in Red-Black Trees
1,Mathematical Background
2,Computer Representation
3,Graph Traversal
4,Topological Sorting
5,A Greedy Algorithm,Shortest
Paths6,Minimal Spanning Trees
7,Graphs as Data Structures
12.1 Mathematical Background
Definitions and Examples
1,A graph G consists of a set V,whose members are
called the vertices of G,together with a set E of pairs
of distinct vertices from V,
2,The pairs in E are called the edges of G.
3,If e = (v,w) is an edge with vertices v and w,then v
and w are said to lie on e,and e is said to be incident
with v and w.
4,If the pairs are unordered,G is called an undirected
graph.
5,If the pairs are ordered,G is called a directed graph,
The term directed graph is often shortened to
digraph,and the unqualified term graph usually
means undirected graph.
依附于 关联
6,Two vertices in an undirected graph are called
adjacent if there is an edge from the first to the
second.
7,A path is a sequence of distinct vertices,each
adjacent to the next.
8,A cycle is a path containing at least three vertices
such that the last vertex on the path is adjacent to
the first.
9,A graph is called connected if there is a path from
any vertex to any other vertex.
10,A free tree is defined as a connected undirected
graph with no cycles.
11,In a directed graph a path or a cycle means always
moving in the direction indicated by the arrows,
Such a path (cycle) is called a directed path (cycle).
12.A directed graph is called strongly connected if
there is a directed path from any vertex to any other
vertex,If we suppress the direction of the edges and
the resulting undirected graph is connected,we call
the directed graph weakly connected.
13.The valence of a vertex is the number of edges on
which it lies,hence also the number of vertices
adjacent to it.
Examples of Graphs
Various kinds of undirected graphs
Examples of directed graphs
12.2 Computer Representation
Set Implementations of Digraphs pg.573
Definition A digraph G consists of a set V,called
the vertices of G,and,for all v?V,a subset Av of V,
called the set of vertices adjacent to v.
directed graph
Digraph as a bit-string set:
template <int max_size>
class Digraph
{ int count;
Set<max_size> neighbors[max_size];
};
number of vertices
at most max_sizeSet as a bit string,pg.573
template <int max_set>
struct Set
{ bool is_element[max_set]; };
Digraph as an adjacency table,pg.574
template <int max_size>
class Digraph
{ int count;
bool adjacency[max_size][max_size];
};
Adjacency
matrix
List Implementation of Digraphs
typedef int Vertex;
template <int max_size>
class Digraph
{ int count;
List<Vertex> neighbors[max_size];
};
Array
Of List
class Edge;
class Vertex
{ Edge *first_edge;
Vertex *next_vertex;
};
forward declarationstart of the
adjacency listnext vertex on the linked list
class Edge
{ Vertex *end_point;
Edge *next_edge;
};
vertex to which
the edge pointsnext_edge on the adjacency list
class Digraph
{ Vertex *first_vertex; };
header for the
list of vertices
12.3 Graph Traversal pg.575
1,Methods pg.575
? Depth-first traversal of a graph
is roughly analogous to
preorder traversal of an ordered
tree,Suppose that the traversal
has just visited a vertex v,and
let w1,w2,… wk be the vertices
adjacent to v,Then we shall next
visit w1 and keep w2,… wk
waiting,After visiting w1,we
traverse all the vertices to which
it is adjacent before returning to
traverse w2,… wk,
? Breadth-first traversal of a
graph is roughly analogous
to level-by-level traversal of
an ordered tree,If the
traversal has just visited a
vertex v,then it next visits
all the vertices adjacent to v,
putting the vertices adjacent
to these in a waiting list to
be traversed after all
vertices adjacent to v have
been visited.
2,Depth-First Algorithm pg.577-578
template <int max_size> void Digraph<max_size>::
depth_first(void (*visit)(Vertex &)) const
/* Post,The function *visit has been performed at each
vertex of the Digraph in depth-first order.
Uses,Method traverse to produce the recursive
depth-first order,*/
{ bool visited[max_size];
Vertex v;
for (all v in G) visited[v] = false;
for (all v in G)
if (!visited[v])traverse(v,visited,visit);
}
The recursion is performed in an auxiliary function traverse.
template <int max_size> void Digraph<max_size>::
traverse ( Vertex &v,bool visited[],
void (*visit)(Vertex &) ) const
/* Pre,v is a vertex of the Digraph,
Post,The depth-first traversal,using function*visit,
has been completed for v and for all vertices
that can be reached from v,
Uses,traverse recursively,*/
{ Vertex w;
visited[v] = true;
(*visit)(v);
for(all w adjacent to v)
if(!visited[w])traverse(w,visited,visit);
}
3,Breadth-First Algorithm pg,578
template <int max_size> void Digraph<max_size>::
breadth_first(void (*visit)(Vertex &)) const
{ Queue q; bool visited[max_size]; Vertex v,w,x;
for (all v in G) visited[v] = false;
for (all v in G)
if (!visited[v])
{ q.append(v);
while(!q.empty( ))
{ q.retrieve(w);
if (!visited[w])
{ visited[w] = true; (*visit)(w);
for(all x adjacent to w) q.append(x);
}
q.serve( );
}
}
}
12.4 Topological Sorting pg,579
Let G be a directed graph with no cycles,A
topological order for G is a sequential listing of all
the vertices in G such that,for all vertices v,w ? G,
if there is an edge from v to w,then v precedes w
in the sequential listing.
Directed graph with no directed cycles
Depth-first ordering
Breadth-first ordering
1,Digraph Class,Topological Sort
typedef int Vertex;
template <int graph_size> class Digraph
{ public:
Digraph( );
void read( );
void write( );
// methods to do a topological sort
void depth_sort(List<Vertex> &topological order);
void breadth_sort(List<Vertex> &topological order);
private:
int count;
List <Vertex> neighbors[graph_size];
void recursive depth_sort(Vertex v,bool visited[],
List<Vertex> &topological_order);
}
2,Depth-First Algorithm
template <int graph_size> void Digraph<graph_size>,:
depth sort(List<Vertex> &topological_order)
/* Post,The vertices of the Digraph are placed into List
topological_order with a depth-first traversal of
those vertices that do not belong to a cycle.
Uses,Methods of class List,and function recursive
depth sort to perform depth-first traversal,*/
{ bool visited[graph_size];
Vertex v;
for (v=0; v<count; v++) visited[v]=false;
topological_order.clear( );
for (v=0; v<count; v++)
if (!visited[v])
recursive_depth_sort(v,visited,topological_order);
}
Add v and its successors
into topological_order
template <int graph_size> void Digraph<graph_size>,:
Recursive_depth_sort ( Vertex v,bool *visited,
List<Vertex> &topological_order )
/* Pre,Vertex v of the Digraph does not belong to the
partially completed List topological order,
Post,All the successors of v and finally v itself are
added to topological order with a depth-first search,*/
{ visited[v] = true;
int degree = neighbors[v].size( );
for (int i=0; i<degree; i++)
{ Vertex w; neighbors[v].retrieve(i,w);
if(!visited[w])
recursive_depth_sort(w,visited,topological_order);
}
topological order.insert(0,v);
}
3,Breadth-First Algorithm
template <int graph size> void Digraph<graph size>,:
breadth_sort(List<Vertex> &topological_order)
{ topological_order.clear( );
Vertex v,w;
int predecessor_count[graph size];
for(v=0; v<count; v++) predecessor_count[v] = 0;
for(v=0; v<count; v++)
for(int i=0; i<neighbors[v].size( ); i++)
{ neighbors[v].retrieve(i,w);
predecessor_count[w]++;
}
Queue ready_to_process;
for(v=0; v<count; v++)
if(predecessor_count[v]==0)
ready_to_process.append(v);
Loop over
all edges v-w.
while(!ready_to_process.empty( ))
{ ready_to_process.retrieve(v);
topological_order.insert(topological_order.size( ),v);
for(int j=0; j<neighbors[v].size( ); j++)
{ neighbors[v].retrieve(j,w);
predecessor_count[w]--;
if( predecessor_count[w]==0 )
ready_to_process.append(w);
}
ready_to_process.serve( );
}
}
Traverse
successors of v.
12.5 A Greedy Algorithm,Shortest Paths
1,The problem of shortest paths,pg,583
Given a directed graph in which each edge has a
nonnegative weight or cost,find a path of least
total weight from a given vertex,called the source,
to every other vertex in the graph.
We keep a set S of vertices whose closest
distances to the source,vertex 0,are known
and add one vertex to S at each stage,We
maintain a table distance that gives,for each
vertex v,the distance from 0 to v along a path
all of whose vertices are in S,except possibly
the last one,To determine what vertex to add to
S at each step,we apply the greedy criterion of
choosing the vertex v with the smallest distance
recorded in the table distance,such that v is not
already in distance.
2,Method,pg,584
Finding a Shortest Path
? Choose the vertex v with the smallest distance
recorded in the table distance,such that v is not
already in distance,
? Prove that the distance recorded in distance
really is the length of the shortest path from source
to v,For suppose that there were a shorter path
from source to v,such as shown below.
This path first leaves S to go to some vertex x,
then goes on to v (possibly even reentering S
along the way),But if this path is shorter than
the colored path to v,then its initial segment
from source to x is also shorter,so that the
greedy criterion would have chosen x rather than
v as the next vertex to add to S,since we would
have had distance[x] < distance[v].
See Pg 584,Fig.12.9
? When we add v to S,we think of v as now colored
and also color the shortest path from source to v,
Next,we update the entries of distance by
checking,for each vertex w not in S,whether a
path through v and then directly to w is shorter
than the previously recorded distance to w.
3,Example of Shortest Path
pg.585 fig.12.10
4,Implementation pg.586
template <class Weight,int graph_size>
class Digraph
{ public:
Digraph();
PrintPath();
void set_distances(Vertex source,Weight distance[ ]) ;
protected:
int count;
Weight adjacency[graph_size][graph_size];
};
template <class Weight,int graph_size>
void Digraph<Weight,graph_size>,,
set distances(Vertex source,Weight distance[ ]) const
{ Vertex v,w; bool found[graph_size];
for (v = 0; v < count; v++)
{ found[v] = false;
distance[v] = adjacency[source][v];
}
found[source] = true; distance[source] = 0;
for ( int i = 0; i < count; i++)
{ Weight min = infinity;
for (w = 0; w < count; w++)
if (!found[w])
if (distance[w] < min)
{ v = w; min = distance[w]; }
found[v] = true;
Vertices found
in S
Initialize with
vertex source
alone in the set S.
Add one vertex
v to S on each pass.
for (w = 0; w < count; w++)
if (!found[w])
if (min + adjacency[v][w] < distance[w])
distance[w] = min + adjacency[v][w];
}
}
12.6 Minimal Spanning Trees pg.587
1,The problem, pg,587
? Shortest paths from source 0 to all vertices in a
network.
? If the original network is based on a connected
graph G,then the shortest paths from a particular
source vertex to all other vertices in G form a tree
that links up all the vertices of G.
? A (connected) tree that is build up out of all the
vertices and some of the edges of G is called a
spanning tree of G.
DEFINITION A minimal spanning tree of a connected
network is a spanning tree such that the sum of the weights
of its edges is as small as possible.
2,Method,pg,589
Spanning Trees see pg,589 Fig,12.12
? Prim's Algorithm for Minimal Spanning Trees
? Kruskal's Algorithm for Minimal Spanning Trees
Prim's Algorithm for Minimal Spanning Trees
? Start with a source vertex,Keep a set X of those
vertices whose paths to source in the minimal
spanning tree that we are building have been found,
Keep the set Y of edges that link the vertices in X in
the tree under construction,The vertices in X and
edges in Y make up a small tree that grows to
become our final spanning tree.
? Initially,source is the only vertex in X,and Y is
empty,At each step,we add an additional vertex to
X,This vertex is chosen so that an edge back to X
has as small as possible a weight,This minimal
edge back to X is added to Y.
?For implementation,we shall keep the vertices in
X as the entries of a Boolean array component,We
keep the edges in Y as the edges of a graph that
will grow to give the output tree from our program.
? We maintain an auxiliary table neighbor that gives,
for each vertex v,the vertex of X whose edge to v
has minimal cost,We also maintain a second table
distance that records these minimal costs,If a
vertex v is not joined by an edge to X we shall
record its distance as the value infinity,The table
neighbor is initialized by setting neighbor[v] to
source for all vertices v,and distance is initialized
by setting distance[v] to the weight of the edge
from source to v if it exists and to infinity if not.
?To determine what vertex to add to X at each step,
we choose the vertex v with the smallest value
recorded in the table distance,such that v is not
already in X,After this we must update our tables
to reflect the change that we have made to X,We
do this by checking,for each vertex w not in X,
whether there is an edge linking v and w,and if so,
whether this edge has a weight less than
distance[w],In case there is an edge(v,w) with this
property,we reset neighbor[w] to v and distance[w]
to the weight of the edge.
Example of Prim's Algorithm Pg.591
Function split node,Action
template <class Record,int order>
void B_tree<Record,order>::split_node (
B_node<Record,order> *current,
const Record &extra_entry,
B_node<Record,order> *extra_branch,
int position,
B_node<Record,order> * &right_half,
Record &median )
/* Pre,current points to a node of a B_tree,The node *current is
full,but if there were room,the record extra_entry with its
right-hand pointer extra_branch would belong in *current
at position position,0 ? position < order,
Post,The node*current with extra_entry and pointer
extra_branch at position position are divided into nodes
*current and *right_half separated by a Record median.
*/
Point to
node to be split
new_entry to insertPoint tosubtree on right
of extra_entry
index in node
where extra_entry
goes
Point to new node
for right_half
of entries
med an entry
(in neither half)
{ right_half->data[i-mid] = current->data[i];
right_half->branch[i+1-mid] = current->branch[i+1];
}
current->count = mid;
right_half->count = order-1-mid;
push_in(right_half,extra_entry,extra_branch,position-mid);
}
median = current->data[current->count-1];
right_half->branch[0] = current->branch[current->count];
current->count--;
}
Remove median
from left half
has more than the minimum number of entries,then
one of them can be moved into the parent node,and
the entry from the parent moved into the leaf where the
deletion is occurring.
?If the adjacent leaf has only the minimum number of
entries,then the two leaves and the median entry from
the parent can all be combined as one new leaf,which
will contain no more than the maximum number of
entries allowed.
?If this step leaves the parent node with too few entries,
then the process propagates upward,In the limiting
case,the last entry is removed from the root,and then
the height of the tree decreases.
pg.549 fig.11.14
Public Deletion Method
template <class Record,int order>
Error_code B tree<Record,order>::
remove(const Record &target)
/*Post,If a Record with Key matching that of target belongs
to the B-tree,a code of success is returned and the
corresponding node is removed from the B-tree,
Otherwise,a code of not_present is returned,*/
{ Error_code result;
result = recursive_remove(root,target);
if( root!=NULL && root->count==0 )
{ B_node<Record,order> *old_root = root;
root = root->branch[0]; delete old_root;
}
return result;
}
root is now empty
Recursive Deletion
template <class Record,int order> Error_code
B_tree<Record,order>:,recursive_remove
(B_node<Record,order> *current,const Record &target)
{ Error_code result; int position;
if( current==NULL) return not_present;
if ( search_node(current,target,position)==success ) // 1
{ result = success;
if( current->branch[position]!=NULL ) // ?
{ copy_in_predecessor(current,position);
recursive_remove ( current->branch[position],
current->data[position] );
} // end ?
else remove_data(current,position);
} // end 1
else result=recursive_remove( current->branch[position],
target );
The target is
in the current node
not at a leaf nodeRemove fr m
a leaf node
if( current->branch[position]!=NULL )
if( current->branch[position]->count<(order-1)/2 )
restore(current,position);
return result;
}
Auxiliary Functions
Remove data from a leaf:
template <class Record,int order>
void B_tree<Record,order>::remove_data (
B_node<Record,order> *current,int position )
{ for( int i=position; i< current->count-1; i++ )
current->data[i]=current->data[i+1];
current->count--;
}
Replace data by its immediate predecessor:
template <class Record,int order>
void B_tree < Record,order >::copy_in_predecessor (
B_node<Record,order> *current,int position )
{ B_node<Record,order> *leaf=current->branch[position];
while( leaf->branch[leaf->count]!= NULL )
leaf = leaf->branch[leaf->count];
current->data[position] = leaf->data[leaf->count-1];
}
Restore Minimum Number of Entries
(pg.552 Fig.11.15)
Function to Restore Minimum Node Entries
template <class Record,int order>
void B_tree<Record,order>::
restore(B_node<Record,order> *current,int position)
{ if(position == current->count)
if( current->branch[position-1]->count>(order-1)/2 )
move_right(current,position-1);
else combine(current,position);
else if( position==0 )
if(current->branch[1]->count>(order-1)/2)
move_left(current,1);
else combine(current,1);
else if( current->branch[position-1]->count>(order-1)/2 )
move_right(current,position-1);
else if( current->branch[position+1]->count>(order-1)/2 )
move_left(current,position+1);
else combine(current,position);
}
case,right
most branch
case,left
st rremaining cases:intermediate branches
Function move_left pg553.
template <class Record,int order>
void B_tree<Record,order>,,move_left(
B_node<Record,order> *current,int position)
{ B_node<Record,order>
*left_branch = current->branch[position-1],
*right_branch = current->branch[position];
left_branch->data[left_branch->count] =
current->data[position-1];
left_branch->branch[++left_branch->count] =
right_branch->branch[0];
current->data[position-1] = right_branch->data[0];
right_branch->count--;
Declare pointer
Take entry
from the parentAdd the right-handentry to the parent
for(int i=0; i<right_branch->count; i++)
{ right_branch->data[i] = right_branch->data[i+1];
right_branch->branch[i] = right_branch->branch[i+1];
}
right_branch->branch[right_branch->count] =
right_branch->branch[right_branch->count+1];
}
Move right-hand entries
to fill the hole
Function move_right pg554.
template <class Record,int order>
void B_tree<Record,order>::
move_right(B_node<Record,order> *current,int position)
{B_node<Record,order>
*left_branch=current->branch[position],
*right_branch=current->branch[position+1];
right_branch->branch[right_branch->count+1] =
right_branch->branch[right_branch->count];
for(int i=right_branch->count; i>0; i--)
{ right_branch->data[i] = right_branch->data[i-1];
right_branch->branch[i] = right_branch->branch[i-1];
}
right_branch->count++;
right_branch->data[0] = current->data[position];
right_branch->branch[0] =
left_branch->branch[left_branch->count--];
current->data[position] =
left_branch->data[left_branch->count];
}
Make room
for new entry
Take entry
from parent
Function combine pg554.
template <class Record,int order>
void B_tree<Record,order>::
combine(B_node<Record,order> *current,int position)
{ B_node<Record,order>
*left_branch = current->branch[position-1],
*right_branch = current->branch[position];
left_branch->data[left_branch->count] =
current->data[position-1];
left_branch->branch[++left_branch->count] =
right_branch->branch[0];
for(int i=0; i<right_branch->count; i++)
{ left_branch->data[left_branch->count] =
right_branch->data[i];
left_branch->branch[++left_branch->count] =
right_branch->branch[i+1];
}
current->count--;
for(i=position-1; i<current->count; i++)
{ current->data[i] = current->data[i+1];
current->branch[i+1] = current->branch[i+2];
}
delete right_branch;
}
11.4 Red-Black Trees
1,Introduction
RedBlack
Red-Black Trees as B-Trees of Order 4
See pg.557 Fig,11.16
Red-Black Trees as B-Trees of Order 4
? Start with a B-tree of order 4,so each node contains 1,2,or
3 entries.
? Convert a node with 3 entries into a binary search tree by:
? A node with two entries has two possible conversions:
? A node with one entry remains unchanged.
Red-Black Trees as Binary Search Trees
? A red-black tree is a binary search tree,with links
colored red or black,obtained from a B-tree of
order 4 by the above conversions.
? Searching and traversal of a red-black tree are
exactly the same as for an ordinary binary search
tree.
?Insertion and deletion,require care to maintain
the underlying B-tree structure,
? Each node of a red-black tree is colored with the
same color as the link immediately above it,We
thus need keep only one extra bit of information
for each node to indicate its color.
The Black Condition
Every simple path from the root to an empty
subtree goes through the same number of black
nodes.
? We adopt the convention that the root is colored
black and all empty subtrees (corresponding to
NULL links) are colored black.
?The B-tree requirement that all its empty subtrees
are on the same level becomes:
? To guarantee that no more than three nodes are
connected by red links as one B-tree node,and
that nodes with three entries are a balanced binary
tree,we require:
The Red Condition
If a node is red,then its parent exists and is black.
? We can now define:
Definition A red-black tree is a binary search tree
in which each node has either the color red or
black and that satisfies the black and red
conditions.
Analysis of Red-Black Trees
Theorem 11.2 The height of a red-black tree
containing n nodes is no more than 2lgn.
?Searching a red-black tree with n nodes is O(log n)
in every case.
?The time for insertion is also O(logn)
[ To show this,we first need to devise the
insertion algorithm,]
? An AVL tree,in its worst case,has height about
1.44 lgn and,on average,has an even smaller
height,Hence red-black trees do not achieve as
good a balance as AVL trees.
?Red-black trees are not necessarily slower than
AVL trees,since AVL trees may require many more
rotations to maintain balance than red-black trees
require.
Red-Black Tree Specification
? The red-black tree class is derived from the
binary search tree class.
? We begin by incorporating colors into the nodes
that will make up red-black trees:
enum Color { red,black };
template <class Record>
struct RB_node, public Binary_node<Record>
{ Color color;
RB_node(const Record &new_entry)
{ color=red; data=new_entry; left=right= NULL; }
RB_node( )
{ color = red; left = right = NULL; }
void set_color(Color c)
{ color = c; }
Color get_color( ) const
{ return color; }
};
? Note the inline definitions for the constructors and
other methods of a red-black node.
Modified Node Specification
? To invoke get color and set color via pointers,
we must add virtual functions to the base struct
Binary node.
? The modified node specification is:
template <class Entry> struct Binary_node
{ Entry data;
Binary_node<Entry> *left,*right;
virtual Color get color( ) const { return red; }
virtual void set color(Color c) { }
Binary_node( ) { left = right = NULL; }
Binary_node(const Entry &x)
{data = x; left = right = NULL; }
};
? With this modification,we can reuse all
the methods and functions for manipulating
binary search trees and their nodes.
Red-Black Trees Insertion
?We begin with the standard recursive algorithm
for insertion into a binary search tree,The new
entry will be in a new leaf node.
?The black condition requires that the new node
must be red.
?If the parent of the new red node is black,then
the insertion is finished,but if the parent is red,
then we have introduced a violation of the red
condition into the tree.
?The major work of the insertion algorithm is to
remove a violation of the red condition,and we
shall find several different cases that we shall
need to process separately.
? We postpone this work as long as we can,When
we make a node red,we do not check the conditions
or repair the tree,Instead,we return from the
recursive call with a status indicator showing that
the node just processed is red.
? After this return,we are processing the parent
node.
?If the parent is black,then the conditions for a red-
black tree are satisfied and the process terminates.
?If the parent is red,then we set the status variable
to show two red nodes together,linked as left child
or as right child,Return from the recursive call.
?We are now processing the grandparent node,
Since the root is black and the parent is red,this
grandparent must exist,By the red condition,this
grandparent is black since the parent was red.
? At the recursive level of the grandparent node,we
transform the tree to restore the red-black
conditions,using cases depending on the relative
positions of the grandparent,parent,and child
nodes,See following diagram.
Insertion Method Implementation pg 561.
template <class Record>
class RB_tree,public Search_tree<Record>
{ public:
Error_code insert(const Record & new_entry);
private,
RB_code rb_insert ( Binary_node<Record>*&,
const Record& );
RB_code modify_left ( Binary_node<Record>*&,
RB_code&);
RB_code modify_right ( Binary_node<Record>*&,
RB_code&);
};
Status indicator values,pg 563
enum RB_code{okay,red_node,left_red,right_red,duplicate};
/* okay,The color of the current root(of the subtree) has not
changed; the tree now satisfies the conditions for a red-
black tree.
red_node,The current root has changed from black to red;
modification may or may not be needed to restore the red-
black properties.
right_red,The current root and its right child are now both
red; a color flip or rotation is needed.
left_red,The current root and its left_child are now both
red; a color flip or rotation is needed.
duplicate,The entry being inserted duplicates another entry;
this is an error.
*/
Public Insertion Method pg 563.
template <class Record>
Error_code RB_tree<Record>::
insert(const Record &new_entry)
/* Post,If the key ofnew_entry is already in the RB_tree,
a code of duplicate error is returned,
Otherwise,a code of success is returned and the
Record new_entry is inserted into the tree in such a
way that the properties of an RB-tree have been
preserved.
Uses,Methods of struct RB_node and recursive function
rb_insert, */
{ RB_code status = rb_insert(root,new_entry);
switch (status)
{ case red_node:
root->set_color(black);
case okay,return success;
case duplicate,return duplicate_error;
case right_red:
case left_red:
cout << "WARNING,Program error in
RB_tree::insert" << endl;
return internal_error;
}
} Convert private
RB_code to
public Error_code.
Always split
the root node
to keep it blackSee pg,562 Fig,11.17
Recursive Insertion Function pg 563.
template <class Record>
RB_code RB_tree<Record>::
rb_insert ( Binary_node<Record>* ¤t,
const Record &new_entry)
/* Pre,current is either NULL or points to the first node of a
subtree of an RB_tree
Post,If the key of new_entry is already in the subtree,a
code of duplicate is returned,
Otherwise,the Record new_entry is inserted into the
subtree pointed to by current,
The properties of a red-black tree have been restored,
except possibly at the root current and one of its
children,whose status is given by the output RB_code,
*/
{ RB_code status,child_status;
if( current==NULL )
{ current = new RB_node<Record>(new_entry);
status = red_node;
}
else if( new_entry==current->data ) return duplicate;
else if( new_entry<current->data)
{ child_status = rb_insert(current->left,new_entry);
status = modify_left(current,child_status);
}
else { child_status = rb_insert(current->right,new_entry);
status = modify_right(current,child_status);
}
return status;
}
Checking the Status,Left Child pg 563.
template <class Record>
RB_code RB_tree<Record>::
modify_left ( Binary_node<Record>* ¤t,
RB_code &child_status)
/* Pre,An insertion has been made in the left_subtree of
*current that has returned the value of child_status
for this subtree.
Post,Any color change or rotation needed for the tree
rooted at current has been made,and a status code
is returned.
Uses,Methods of struct RB_node,with rotate_right,
double_rotate_right,and flip_color,*/
{ RB_code status = okay;
Binary_node<Record> *aunt = current->right;
Color aunt_color = black;
if(aunt != NULL) aunt_color = aunt->get_color( );
switch (child_status)
{ case okay,break;
case red_node:
if(current->get_color()==red) status = left_red;
else status = okay;
break;
case left_red:
if( aunt_color==black ) status = rotate_right(current);
else status = flip_color(current);
break;
No action needed,
as tree is already OKcurrent is black,left is red,so OK
case right_red:
if( aunt_color==black )
status = double rotate_right(current);
else status = flip_color(current);
break;
}
return status;
}
Red-Black Trees
Insert 15 in Red-Black Trees
