	
		
		
		
	
Tree-Based Containers
	This section describes tree-based containers. It is organized as follows.
	
 #overviewOverview  describes an overview.	
 #invariantsNode Invariants  describes node invariants.	
 #add_methodsAdditional Types and Methods  describes additional methods
that tree-based containers support.
Overview 
	Figure
#tree_cdTree-based containers 	shows the container-hierarchy; the tree-based container is circled.
no image
Tree-based containers.
	The tree-based container has the following declaration:
template<
	
typename Key,
	
typename Data,
	
class Cmp_Fn = std::less<Key>,
	
class DS_Tag = rb_tree_ds_tag.htmlrb_tree_ds_tag ,
	
class Node_Updator = null_node_updator.htmlnull_node_updator ,
	
class Allocator =
		std::allocator<
char> >
class tree_assoc_cntnr.htmltree_assoc_cntnr ;
	The parameters have the following meaning:
	
 Key is the key type.
	
	
 Data is the data-policy, and is explained in
ms_gen.html#ds_policyMapping-Semantics Genericity::Data Types as a Policy .
	
	
 Cmp_Fn is a key comparison functor	
 DS_Tag specifies which underlying data-structure to use, and is described shortly.
	
 Node_Updator is a policy for updating node invariants.
This is described in 
#invariantsNode Invariants .
	
	
 Allocator is (surprisingly) an allocator type.
	
	The 
DS_Tag specifies which underlying data-structure to use.
Instantiating it by
rb_tree_ds_tag.htmlrb_tree_ds_tag ,
splay_tree_ds_tag.htmlsplay_tree_ds_tag ,
or
ov_tree_ds_tag.htmlov_tree_ds_tag ,
specifies an undelying
red-black tree,
splay tree,
or
ordered-vector tree.
	any other tag is illegal. Note that containers based on the former two contain more types and methods than the latter (
e.g., reverse_iterator and rbegin), and different exception and invalidation guarantees.
Node Invariants 
	Figure
#node_invariantsSome node invariants shows some node invariants. A shows
a tree whose each node contains, asides from an 
double key, the number
of nodes at the subtree rooted at the node; B shows a tree whose each node
contains, asides from a line-interval key, the maximal endpoint of the interval
of any node in the subtree rooted at the node.
	The first tree allows querying efficiently what is the order statistic
of any element; the second tree allows querying efficiently if any, or which,
intervals overlap a given interval.
no image 
Some node invariants.
	Maintaining such trees is difficult, for two reasons:
	
 Various operations can invalidate node invariants.
E.g., Figure
#node_invariant_invalidationsInvalidation of node invariants shows how a right rotation, performed on A, results in B, with nodes 
xand 
y having corrupted invariants (the greyed nodes in C);
Figure
#node_invariant_invalidationsInvalidation of node invariants shows how an insert, performed on D, results in E, with nodes 
xand 
y having corrupted invariants (the greyed nodes in F).
	It is not feasible to know outside the tree the effect of an operation on the
nodes of the tree.
	
	
		Even if node invariants are maintained, it is not possible to know
in advance which search paths are required (
e.g., searching for all
line intervals overlapping some interval might require several search paths).
	
no image 
Invalidation of node invariants.
	These problems are solved by a combination of two means:
	
		The tree-based containers are parameterized by a 
Node_Updatorparameter. When a tree operation might invalidate some node invariant,
a 
Node_Updator object is invoked to restore the invariant. This object is
always invoked with three nodes: some node, say 
x in
Figure
#restoring_node_invariantsInvalidation of node invariants -A
has an invalid invariant, but its children, 
y and z hav valid invariants.
After the invocation, all three nodes have valid invariants, as
in
Figure
#restoring_node_invariantsInvalidation of node invariants -B.
It is well known that any 
insert, erase,
split or join, can restore
all node invariants by a small number of node invariant updates
[
references.html#clrs2001clrs2001 ].
For example, Figure
#update_seq_diagramInsert update sequence diagram
shows an 
insert operation (point A); the tree performs some operations, and
calls the update functor three times (points B, C, and D).
	
	
		The tree based containers all define internally 
node_iterator	and 
const_node_iterator, iterators which can be used to traverse
	from a node to any of its children or parent.
	
no image 
Invalidation of node invariants.
no image 
Insert update sequence diagram.
	In
concepts.html#concepts_null_policiesNull Policy Classes a distinction was made between 
redundant policiesand 
null policies.
	Seemingly, in this case a redundant policy - a policy which doesn't
affect nodes' contents would suffice in this case. This, however, would
lead to performance loss.
Figure
#rationale_null_node_updatorRationale for null node-invariant functors
shows a typical case where invariants are restored (in this case, to the
shaded node). In most cases, tree operations such as rotations affect only
the lower levels of the tree. A null policy allows to know that there
is no need to traverse the tree to the root.
no image 
Rationale for null node-invariant functors.
Addtional Methods 
