Chapter 11 MULTIWAY TREES
1,Orchards,Trees,and Binary
Trees
2,Lexicographic Search Trees,
Tries
3,External Searching,B-Trees
4,Red-Black Trees
Pointers and Pitfalls
11.1 On the Classification of Species
Definition:
1,On the Classification of Species
?A (free) tree is any set of points (called vertices) and
any set of pairs of distinct vertices (called edges or
branches) such that (1) there is a sequence of edges (a
path) from any vertex to any other,and (2) there are no
circuits,that is,no paths starting from a vertex and
returning to the same vertex.
?An ordered tree is a rooted tree in which the children
of each vertex are assigned an order.
?A forest is a set of trees,We usually assume that all
trees in a forest are rooted.
?An orchard (also called an ordered forest) is an
ordered set of ordered trees.
2,Ordered Trees
?A rooted tree is a tree in which one vertex,called the
root,is distinguished.
See pg.522 Fig.11.1
3,Forests and Orchards
?Multiple links
?first child and next sibling links
?Correspondence with binary trees
Recursive Definitions
Definition A rooted tree consists of a single vertex v,
called the root of the tree,together with a forest F,
whose trees are called the subtrees of the root.
A forest F is a (possibly empty) set of rooted trees.
Definition An ordered tree T consists of a single
vertex v,called the root of the tree,together with an
orchard O,whose trees are called the subtrees of the
root v,We may denote the ordered tree with the
ordered pair T = {v,O}.
An orchard O is either the empty set ;,or consists of
an ordered tree T,called the first tree of the orchard,
together with another orchard O’ (which contains the
remaining trees of the orchard),We may denote the
orchard with the ordered pair O = (T,O’).
4,The Formal Correspondence
Definition A binary tree B is either the empty set ; or
consists of a root vertex v with two binary trees B1
and B2, We may denote the binary tree with the
ordered triple B = [v;B1;B2].
Theorem 11.1 Let S be any finite set of vertices,There
is a one-to-one correspondence f from the set of
orchards whose set of vertices is S to the set of
binary trees whose set of vertices is S.
Proof,Define f (?) = ?
Define f ({v,O1},O2 ) = [ v,f(O1),f(O2) ]
Show by mathematical induction on the number of
vertices that f is a one-to-one correspondence.
数学归纳法
5.Rotations
? Draw the orchard so that the first child of each
vertex is immediately below the vertex.
? Draw a vertical link from each vertex to its first child,
and draw a horizontal link from each vertex to its
next sibling.
? Remove the remaining original links.
? Rotate the diagram 45 degrees clockwise,so that
the vertical links appear as left links and the
horizontal links as right links.
6,Summary
Orchards and binary trees correspond by any of:
? first child and next sibling links,
? rotations of diagrams,
? formal notational equivalence.
11.2 Lexicographic Search Trees,Tries
Definition:
A trie of order m is either empty or consists of
an ordered sequence of exactly m tries of order
m.
1,Tries Definitions pg.530
2,Seach for a Key pg.530
3,C++ Tries Declarations pg.531-532
?Every Record has a Key that is an alphanumeric string.
?Method char key letter(int position) returns the
character in the given position of the key or returns a
blank,if the key has length less than position.
?Auxiliary function int alphabetic order(char symbol)
returns the alphabetic position of the character symbol,
or 27 for nonblank,nonalphabetic characters,or 0 for
blank characters.
const int num_chars = 28;
struct Trie_node
{ Record *data;
Trie_node *branch[num_chars];
Trie_node();
};
data membersconstructors
class Trie
{ public,
Trie();
bool empty();
Error_code trie_search(const Key &target,Record &x)
const;
Error_code insert(const Record &new_entry);
void inorder(void (*visit)(Record *));
int size();
int height();
void clear();
~Trie();
void depth_traverse(void (*visit)(Record *));
Error_code remove(const Key &target);
private:
Trie_node *root;
};
4,Searching a Tries pg.532
Error_code Trie::trie_search(const Key &target,Record &x)
/* Post,If the search is successful,a code of success is
returned,and the output parameter x is set as a
copy of the Trie's record that holds target.
Otherwise,a code of not_present is returned.
Uses,Methods of class Key,*/
{ int position = 0; char next_char;
Trie_node *location = root;
while (location != NULL &&
(next_char=target.key_letter(position)) != ' ')
{ location=location->branch[alphabetic_order(next_char)];
position++;
}
indexes letters
of key
Terminate search
for a NULL location
Terminate search
for a blank
in the target
Move down
the appropriate branch
of the trie
Move to
the next character
of the target
if (location != NULL && location->data != NULL)
{ x = *(location->data); return success; }
else return not_present;
}
5,Insertion into a Tries pg.533
Error_code Trie::insert(const Record &new_entry)
/* Post,If the Key of new_entry is already in the Trie,
a code of duplicate_error is returned.
Otherwise,a code of success is returned and
the Record new_entry is inserted into the Trie.
Uses,Methods of classes Record and Trie_node.*/
{ Error_code result = success;
if (root==NULL) root = new Trie_node;
Create a new
empty Trie
int position = 0; char next_char;
Trie_node *location = root;
while (location != NULL &&
(next_char=target.key_letter(position)) != ' ')
{ int next_position = alphabetic_order(next_char);
if (location->branch[next_position] == NULL)
location->branch[next_position]=new Trie_node;
location = location->branch[next_position];
position++;
}
if (location->data != NULL) result = duplicate_error;
else location->data = new Record(new_entry);
return result;
} indexes letters
of new_entrymoves through the Trie
At this point,
we have tested
for all non blank
characters of
new_entry.
The number of steps required to search a trie
or insert into it is proportional to the number
of characters making up a key,not to a
logarithm of the number of keys as in other
tree-based searches.
6,Deletion from a Tries pg.533
Error_code Trie::trie_search(const Key &target,Record &x)
/* Post,If the search is successful,a code of success is
returned,and the output parameter x is set as a
copy of the Trie's record that holds target.
Otherwise,a code of not_present is returned.
Uses,Methods of class Key,*/
{ int position = 0; char next_char;
Trie_node *location = root;
while (location != NULL &&
(next_char=target.key_letter(position)) != ' ')
{ location=location->branch[alphabetic_order(next_char)];
position++;
}
11.3 External Searching,B-Trees
? An m-way search tree is a tree in which,for
some integer m called the order of the tree,
each node has at most m children.
? If k≤ m is the number of children,then the node
contains exactly k-1 keys,which partition all
the keys into k subsets consisting of all the
keys less than the first key in the node,all the
keys between a pair of keys in the node,and all
keys greater than the largest key in the node.
阶
1,Multiway Search Trees
定义,一颗 m阶查找树, 或者是一颗空树, 或者是满
足如下性质的 m路查找树：
1)每个结点最多有 m棵子树, m-1个关键字, 其结构
为：
其中 n为关键字个数, Pi 为指向子树根结点的指针,
Ki为关键字 。
2) Ki<Ki+1,
3) 子树 Pi中的所有关键字均大于 Ki,小于 Ki+1,
4) 子树 P0中的关键字均小于 Ki,而子树 Pn中的所
有关键字均大于 Kn。
5） 子树 Pi也是 m阶查找树, 0≤i≤n。
2,Balanced Multiway Trees (B-Trees)
Definition A B-tree of order m is an m-way search
tree in which
1,All leaves are on the same level.
2,All internal nodes except the root have at most
m nonempty children,and at least nonempty
children.
3,The number of keys in each internal node is one
less than the number of its nonempty children,
and these keys partition the keys in the children in
the fashion of a search tree.
4,The root has at most m children,but may have
as few as 2 if it is not a leaf,or none if the tree
consists of the root alone.
? ?m/2
定义, 一棵 m阶的 B-树, 或为空树, 或为满足下列特性的 m
叉树：
① 每个结点至多有 m棵子树；
② 除根结点和叶结点外, 其它每个结点至少有 ?m/2?棵子树；
③ 除非根结点为最低层非终端结点, 否则至少有两棵子树；
④ 所有非终端结点中包含有下列信息：
（ n,A0,k1,A1,K2,A2,…, Kn,An）
其中, Ki（ 1? i ?n） 为关键字, 且 Ki<Ki+1（ 1? i <n）, Ai
（ 0? i ?n） 为指向子树根结点的指针, 且指针 Ai（ 0? i<n） 所
指子树中所有结点的关键字均小于 Ki+1,指针 An 所指子树中
的关键字均大于 Kn,n（ n= ?m/2? ? m-1） 为关键字的个数；
⑤ 所有的叶子结点都出现在同一层上, 并且不带信息 （ 可以看
作是外部结点或查失败的结点,实际上这些结点不存在,指向这
些结点的指针为空 ） 。
3,Insertion into a B-Tree
In contrast to binary search trees,B-trees are not
allowed to grow at their leaves; instead,they are
forced to grow at the root,General insertion
method:
1,Search the tree for the new key,This search (if
the key is truly new) will terminate in failure at a
leaf.
2,Insert the new key into to the leaf node,If the
node was not previously full,then the insertion is
finished.
3,When a key is added to a full node,then the
node splits into two nodes,side by side on the
same level,except that the median key is not put
into either of the two new nodes.
4,When a node splits,move up one level,insert
the median key into this parent node,and repeat
the splitting process if necessary.
5,When a key is added to a full root,then the root
splits in two and the median key sent upward
becomes a new root,This is the only time when
the B-tree grows in height.
Growth of a B-Tree
The growth of a B-Tree of order 5 pg.538 Fig.11.10
We add the order as a second template parameter,For
example,B_tree<int,5> sample tree; declares sample
tree as a B_tree of order 5 that holds integer records.
B_tree class declaration:
template <class Record,int order>
class B_tree
{ public,
// Add public methods.
private,
// data members
B_node<Record,order> *root;
// Add private auxiliary functions here.
};
4,B-Tree Declarations in C++
template <class Record,int order>
struct B_node
{ B_node( );
private:
// data members:
int count;
Record data[order-1];
B_node<Record,order> *branch[order];
};
B-Tree Node declaration,记录数记录数组
指针数组
Conventions:
?count gives the number of records in the B_node.
?If count is nonzero then the node has count+1
children,
? branch[0] points to the subtree containing all
records with keys less than that in data[0].
?For 1 ? position ? count-1,branch[position] points
to the subtree with keys strictly between those in
the subtrees pointed to by data[position-1] and
data[position].
?branch[count] points to the subtree with keys
greater than that of data[count-1].
参看“幻灯片 25”中文定义。
5,Searching and insertion pg.539
template <class Record,int order>
Error_code B_tree<Record,order>::
search_tree(Record &target)
{ B_node<Record,order> *sub_root=root;
while(sub_root != NULL)
{ int position;
if (search_node(sub_root,target,
position) == not_present )
sub_root=sub_root->branch[position];
else
{ target = sub_root->data[position];
return success;
}
}
return not_present;
}
template <class Record,int order>
Error_code B_tree<Record,order>::search_node
( B_node<Record,order> *current,const Record &target,int &position)
{position=0;
while(position<current->count &&
target>current->data[position]) position++;
if ( position<current->count &&
target==current->data[position] ) return success;
else return not present;
}
引用参数
带回 target
在结点中的位置
Perform a
sequential search
through the keys
? For B-trees of large order,this function should be
modified to use binary search instead of sequential
search.
?Another possibility is to use a linked binary search
tree instead of a sequential array of entries for each
node.
Insertion,Parameters and push down
? Insertion is done with recursion in a function called
push down.
? We require that the record new_entry being inserted
is not already present in the tree.
The recursive function push_down uses three more
output parameters.
? current is the root of the current subtree under
consideration.
? If *current splits to accommodate new entry,push
down
returns a code of overflow,and the following come
into use:
?The old node *current contains the left half of the
entries.
?median gives the median record.
Public Insertion Method
template <class Record,int order> Error_code
B_tree<Record,order>::insert(const Record &new_entry)
{ Record median;
B_node<Record,order> *right_branch,*new_root;
Error_code result =
push_down(root,new_entry,median,right_branch);
if ( result==overflow)
{ new_root = new B_node<Record,order>;
new_root->count=1; new_root->data[0]=median;
new_root->branch[0]=root;
new_root->branch[1]=right branch;
root=new_root; result = success;
}
return result;
}
The whole tree
grows in heightMake a brand new_rootfor the whole B-tree
Recursive Insertion into a Subtree
template <class Record,int order>Error_code
B_tree<Record,order>::push_down (
B_node<Record,order> *current,
const Record &new_entry,
Record &median,
B_node<Record,order>* &right_branch )
{ Error_code result; int position;
if(current==NULL)
{ median=new_entry; right_branch= NULL;
result = overflow; }
else
{ if (search_node(current,new_entry,position)==success)
result=duplicate_error;
else
Since we can’t insert
in an empty tree,the
recursion terminates.
Search the current node.
{ Record extra_entry;
B_node<Record,order> *extra_branch;
result=push_down(current->branch[position],
new_entry,extra_entry,extra branch);
if( result==overflow)
if(current->count<order-1)
{ result=success;
push_in(current,extra_entry,extra_branch,position);
}
else split_node( current,extra_entry,extra_branch,
position,right_branch,median);
}
return result;
}
Record extra_entry
now must be added
to current
Record median and
its right branch will go up
to a higher node
template <class Record,int order>
void B_tree<Record,order>::
push_in ( B_node<Record,order> *current,
const Record &entry,
B_node<Record,order> *right_branch,
int position )
/* Pre,current points to a node of a B_tree, The node
*current is not full and entry belongs in *current at
index position,
Post,entry has been inserted along with its right-hand
branch right_branch into *current at index position,
*/
{ for(int i=current->count; i>position; i--)
{ current->data[i] = current->data[i-1];
current->branch[i+1] = current->branch[i];
}
current->data[position] = entry;
current->branch[position+1] = right_branch;
current->count++;
}
Shift all later data
to the right
Example of Splitting a Full Node
See pg.547 fig.11.13
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 = new B_node<Record,order>;
int mid = order/2;
if ( position <= mid )
{ for(int i=mid; i<order-1; i++)
{ 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(current,extra_entry,extra_branch,position);
}
else
{ mid++;
for(int i=mid; i<order-1; i++)
The entries from
mid on will go to
right_half
First case,
extra_entry belongs
in left half
Move entries to
right_h
Second case,
extra_entry belongs
in right_half.
Temporarily
leave the median
in left half
Move entries
to right_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
6,Deletion from a B-Tree pg.548
?If the entry that is to be deleted is not in a leaf,then its
immediate predecessor (or successor) under the
natural order of keys is guaranteed to be in a leaf.
?We promote the immediate predecessor (or successor)
into the position occupied by the deleted entry,and
delete the entry from the leaf.
?If the leaf contains more than the minimum number of
entries,then one of them can be deleted with no further
action.
?If the leaf contains the minimum number,then we first
look at the two leaves (or,in the case of a node on the
outside,one leaf) that are immediately adjacent to each
other and are children of the same node,If one of these
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,Orchards,Trees,and Binary
Trees
2,Lexicographic Search Trees,
Tries
3,External Searching,B-Trees
4,Red-Black Trees
Pointers and Pitfalls
11.1 On the Classification of Species
Definition:
1,On the Classification of Species
?A (free) tree is any set of points (called vertices) and
any set of pairs of distinct vertices (called edges or
branches) such that (1) there is a sequence of edges (a
path) from any vertex to any other,and (2) there are no
circuits,that is,no paths starting from a vertex and
returning to the same vertex.
?An ordered tree is a rooted tree in which the children
of each vertex are assigned an order.
?A forest is a set of trees,We usually assume that all
trees in a forest are rooted.
?An orchard (also called an ordered forest) is an
ordered set of ordered trees.
2,Ordered Trees
?A rooted tree is a tree in which one vertex,called the
root,is distinguished.
See pg.522 Fig.11.1
3,Forests and Orchards
?Multiple links
?first child and next sibling links
?Correspondence with binary trees
Recursive Definitions
Definition A rooted tree consists of a single vertex v,
called the root of the tree,together with a forest F,
whose trees are called the subtrees of the root.
A forest F is a (possibly empty) set of rooted trees.
Definition An ordered tree T consists of a single
vertex v,called the root of the tree,together with an
orchard O,whose trees are called the subtrees of the
root v,We may denote the ordered tree with the
ordered pair T = {v,O}.
An orchard O is either the empty set ;,or consists of
an ordered tree T,called the first tree of the orchard,
together with another orchard O’ (which contains the
remaining trees of the orchard),We may denote the
orchard with the ordered pair O = (T,O’).
4,The Formal Correspondence
Definition A binary tree B is either the empty set ; or
consists of a root vertex v with two binary trees B1
and B2, We may denote the binary tree with the
ordered triple B = [v;B1;B2].
Theorem 11.1 Let S be any finite set of vertices,There
is a one-to-one correspondence f from the set of
orchards whose set of vertices is S to the set of
binary trees whose set of vertices is S.
Proof,Define f (?) = ?
Define f ({v,O1},O2 ) = [ v,f(O1),f(O2) ]
Show by mathematical induction on the number of
vertices that f is a one-to-one correspondence.
数学归纳法
5.Rotations
? Draw the orchard so that the first child of each
vertex is immediately below the vertex.
? Draw a vertical link from each vertex to its first child,
and draw a horizontal link from each vertex to its
next sibling.
? Remove the remaining original links.
? Rotate the diagram 45 degrees clockwise,so that
the vertical links appear as left links and the
horizontal links as right links.
6,Summary
Orchards and binary trees correspond by any of:
? first child and next sibling links,
? rotations of diagrams,
? formal notational equivalence.
11.2 Lexicographic Search Trees,Tries
Definition:
A trie of order m is either empty or consists of
an ordered sequence of exactly m tries of order
m.
1,Tries Definitions pg.530
2,Seach for a Key pg.530
3,C++ Tries Declarations pg.531-532
?Every Record has a Key that is an alphanumeric string.
?Method char key letter(int position) returns the
character in the given position of the key or returns a
blank,if the key has length less than position.
?Auxiliary function int alphabetic order(char symbol)
returns the alphabetic position of the character symbol,
or 27 for nonblank,nonalphabetic characters,or 0 for
blank characters.
const int num_chars = 28;
struct Trie_node
{ Record *data;
Trie_node *branch[num_chars];
Trie_node();
};
data membersconstructors
class Trie
{ public,
Trie();
bool empty();
Error_code trie_search(const Key &target,Record &x)
const;
Error_code insert(const Record &new_entry);
void inorder(void (*visit)(Record *));
int size();
int height();
void clear();
~Trie();
void depth_traverse(void (*visit)(Record *));
Error_code remove(const Key &target);
private:
Trie_node *root;
};
4,Searching a Tries pg.532
Error_code Trie::trie_search(const Key &target,Record &x)
/* Post,If the search is successful,a code of success is
returned,and the output parameter x is set as a
copy of the Trie's record that holds target.
Otherwise,a code of not_present is returned.
Uses,Methods of class Key,*/
{ int position = 0; char next_char;
Trie_node *location = root;
while (location != NULL &&
(next_char=target.key_letter(position)) != ' ')
{ location=location->branch[alphabetic_order(next_char)];
position++;
}
indexes letters
of key
Terminate search
for a NULL location
Terminate search
for a blank
in the target
Move down
the appropriate branch
of the trie
Move to
the next character
of the target
if (location != NULL && location->data != NULL)
{ x = *(location->data); return success; }
else return not_present;
}
5,Insertion into a Tries pg.533
Error_code Trie::insert(const Record &new_entry)
/* Post,If the Key of new_entry is already in the Trie,
a code of duplicate_error is returned.
Otherwise,a code of success is returned and
the Record new_entry is inserted into the Trie.
Uses,Methods of classes Record and Trie_node.*/
{ Error_code result = success;
if (root==NULL) root = new Trie_node;
Create a new
empty Trie
int position = 0; char next_char;
Trie_node *location = root;
while (location != NULL &&
(next_char=target.key_letter(position)) != ' ')
{ int next_position = alphabetic_order(next_char);
if (location->branch[next_position] == NULL)
location->branch[next_position]=new Trie_node;
location = location->branch[next_position];
position++;
}
if (location->data != NULL) result = duplicate_error;
else location->data = new Record(new_entry);
return result;
} indexes letters
of new_entrymoves through the Trie
At this point,
we have tested
for all non blank
characters of
new_entry.
The number of steps required to search a trie
or insert into it is proportional to the number
of characters making up a key,not to a
logarithm of the number of keys as in other
tree-based searches.
6,Deletion from a Tries pg.533
Error_code Trie::trie_search(const Key &target,Record &x)
/* Post,If the search is successful,a code of success is
returned,and the output parameter x is set as a
copy of the Trie's record that holds target.
Otherwise,a code of not_present is returned.
Uses,Methods of class Key,*/
{ int position = 0; char next_char;
Trie_node *location = root;
while (location != NULL &&
(next_char=target.key_letter(position)) != ' ')
{ location=location->branch[alphabetic_order(next_char)];
position++;
}
11.3 External Searching,B-Trees
? An m-way search tree is a tree in which,for
some integer m called the order of the tree,
each node has at most m children.
? If k≤ m is the number of children,then the node
contains exactly k-1 keys,which partition all
the keys into k subsets consisting of all the
keys less than the first key in the node,all the
keys between a pair of keys in the node,and all
keys greater than the largest key in the node.
阶
1,Multiway Search Trees
定义,一颗 m阶查找树, 或者是一颗空树, 或者是满
足如下性质的 m路查找树：
1)每个结点最多有 m棵子树, m-1个关键字, 其结构
为：
其中 n为关键字个数, Pi 为指向子树根结点的指针,
Ki为关键字 。
2) Ki<Ki+1,
3) 子树 Pi中的所有关键字均大于 Ki,小于 Ki+1,
4) 子树 P0中的关键字均小于 Ki,而子树 Pn中的所
有关键字均大于 Kn。
5） 子树 Pi也是 m阶查找树, 0≤i≤n。
2,Balanced Multiway Trees (B-Trees)
Definition A B-tree of order m is an m-way search
tree in which
1,All leaves are on the same level.
2,All internal nodes except the root have at most
m nonempty children,and at least nonempty
children.
3,The number of keys in each internal node is one
less than the number of its nonempty children,
and these keys partition the keys in the children in
the fashion of a search tree.
4,The root has at most m children,but may have
as few as 2 if it is not a leaf,or none if the tree
consists of the root alone.
? ?m/2
定义, 一棵 m阶的 B-树, 或为空树, 或为满足下列特性的 m
叉树：
① 每个结点至多有 m棵子树；
② 除根结点和叶结点外, 其它每个结点至少有 ?m/2?棵子树；
③ 除非根结点为最低层非终端结点, 否则至少有两棵子树；
④ 所有非终端结点中包含有下列信息：
（ n,A0,k1,A1,K2,A2,…, Kn,An）
其中, Ki（ 1? i ?n） 为关键字, 且 Ki<Ki+1（ 1? i <n）, Ai
（ 0? i ?n） 为指向子树根结点的指针, 且指针 Ai（ 0? i<n） 所
指子树中所有结点的关键字均小于 Ki+1,指针 An 所指子树中
的关键字均大于 Kn,n（ n= ?m/2? ? m-1） 为关键字的个数；
⑤ 所有的叶子结点都出现在同一层上, 并且不带信息 （ 可以看
作是外部结点或查失败的结点,实际上这些结点不存在,指向这
些结点的指针为空 ） 。
3,Insertion into a B-Tree
In contrast to binary search trees,B-trees are not
allowed to grow at their leaves; instead,they are
forced to grow at the root,General insertion
method:
1,Search the tree for the new key,This search (if
the key is truly new) will terminate in failure at a
leaf.
2,Insert the new key into to the leaf node,If the
node was not previously full,then the insertion is
finished.
3,When a key is added to a full node,then the
node splits into two nodes,side by side on the
same level,except that the median key is not put
into either of the two new nodes.
4,When a node splits,move up one level,insert
the median key into this parent node,and repeat
the splitting process if necessary.
5,When a key is added to a full root,then the root
splits in two and the median key sent upward
becomes a new root,This is the only time when
the B-tree grows in height.
Growth of a B-Tree
The growth of a B-Tree of order 5 pg.538 Fig.11.10
We add the order as a second template parameter,For
example,B_tree<int,5> sample tree; declares sample
tree as a B_tree of order 5 that holds integer records.
B_tree class declaration:
template <class Record,int order>
class B_tree
{ public,
// Add public methods.
private,
// data members
B_node<Record,order> *root;
// Add private auxiliary functions here.
};
4,B-Tree Declarations in C++
template <class Record,int order>
struct B_node
{ B_node( );
private:
// data members:
int count;
Record data[order-1];
B_node<Record,order> *branch[order];
};
B-Tree Node declaration,记录数记录数组
指针数组
Conventions:
?count gives the number of records in the B_node.
?If count is nonzero then the node has count+1
children,
? branch[0] points to the subtree containing all
records with keys less than that in data[0].
?For 1 ? position ? count-1,branch[position] points
to the subtree with keys strictly between those in
the subtrees pointed to by data[position-1] and
data[position].
?branch[count] points to the subtree with keys
greater than that of data[count-1].
参看“幻灯片 25”中文定义。
5,Searching and insertion pg.539
template <class Record,int order>
Error_code B_tree<Record,order>::
search_tree(Record &target)
{ B_node<Record,order> *sub_root=root;
while(sub_root != NULL)
{ int position;
if (search_node(sub_root,target,
position) == not_present )
sub_root=sub_root->branch[position];
else
{ target = sub_root->data[position];
return success;
}
}
return not_present;
}
template <class Record,int order>
Error_code B_tree<Record,order>::search_node
( B_node<Record,order> *current,const Record &target,int &position)
{position=0;
while(position<current->count &&
target>current->data[position]) position++;
if ( position<current->count &&
target==current->data[position] ) return success;
else return not present;
}
引用参数
带回 target
在结点中的位置
Perform a
sequential search
through the keys
? For B-trees of large order,this function should be
modified to use binary search instead of sequential
search.
?Another possibility is to use a linked binary search
tree instead of a sequential array of entries for each
node.
Insertion,Parameters and push down
? Insertion is done with recursion in a function called
push down.
? We require that the record new_entry being inserted
is not already present in the tree.
The recursive function push_down uses three more
output parameters.
? current is the root of the current subtree under
consideration.
? If *current splits to accommodate new entry,push
down
returns a code of overflow,and the following come
into use:
?The old node *current contains the left half of the
entries.
?median gives the median record.
Public Insertion Method
template <class Record,int order> Error_code
B_tree<Record,order>::insert(const Record &new_entry)
{ Record median;
B_node<Record,order> *right_branch,*new_root;
Error_code result =
push_down(root,new_entry,median,right_branch);
if ( result==overflow)
{ new_root = new B_node<Record,order>;
new_root->count=1; new_root->data[0]=median;
new_root->branch[0]=root;
new_root->branch[1]=right branch;
root=new_root; result = success;
}
return result;
}
The whole tree
grows in heightMake a brand new_rootfor the whole B-tree
Recursive Insertion into a Subtree
template <class Record,int order>Error_code
B_tree<Record,order>::push_down (
B_node<Record,order> *current,
const Record &new_entry,
Record &median,
B_node<Record,order>* &right_branch )
{ Error_code result; int position;
if(current==NULL)
{ median=new_entry; right_branch= NULL;
result = overflow; }
else
{ if (search_node(current,new_entry,position)==success)
result=duplicate_error;
else
Since we can’t insert
in an empty tree,the
recursion terminates.
Search the current node.
{ Record extra_entry;
B_node<Record,order> *extra_branch;
result=push_down(current->branch[position],
new_entry,extra_entry,extra branch);
if( result==overflow)
if(current->count<order-1)
{ result=success;
push_in(current,extra_entry,extra_branch,position);
}
else split_node( current,extra_entry,extra_branch,
position,right_branch,median);
}
return result;
}
Record extra_entry
now must be added
to current
Record median and
its right branch will go up
to a higher node
template <class Record,int order>
void B_tree<Record,order>::
push_in ( B_node<Record,order> *current,
const Record &entry,
B_node<Record,order> *right_branch,
int position )
/* Pre,current points to a node of a B_tree, The node
*current is not full and entry belongs in *current at
index position,
Post,entry has been inserted along with its right-hand
branch right_branch into *current at index position,
*/
{ for(int i=current->count; i>position; i--)
{ current->data[i] = current->data[i-1];
current->branch[i+1] = current->branch[i];
}
current->data[position] = entry;
current->branch[position+1] = right_branch;
current->count++;
}
Shift all later data
to the right
Example of Splitting a Full Node
See pg.547 fig.11.13
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 = new B_node<Record,order>;
int mid = order/2;
if ( position <= mid )
{ for(int i=mid; i<order-1; i++)
{ 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(current,extra_entry,extra_branch,position);
}
else
{ mid++;
for(int i=mid; i<order-1; i++)
The entries from
mid on will go to
right_half
First case,
extra_entry belongs
in left half
Move entries to
right_h
Second case,
extra_entry belongs
in right_half.
Temporarily
leave the median
in left half
Move entries
to right_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
6,Deletion from a B-Tree pg.548
?If the entry that is to be deleted is not in a leaf,then its
immediate predecessor (or successor) under the
natural order of keys is guaranteed to be in a leaf.
?We promote the immediate predecessor (or successor)
into the position occupied by the deleted entry,and
delete the entry from the leaf.
?If the leaf contains more than the minimum number of
entries,then one of them can be deleted with no further
action.
?If the leaf contains the minimum number,then we first
look at the two leaves (or,in the case of a node on the
outside,one leaf) that are immediately adjacent to each
other and are children of the same node,If one of these
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
