[ новости /+++ | форум | теги | ]

NAME

SPLAY_PROTOTYPE

 
SPLAY_GENERATE

 
SPLAY_ENTRY

 
SPLAY_HEAD

 
SPLAY_INITIALIZER

 
SPLAY_ROOT

 
SPLAY_EMPTY

 
SPLAY_NEXT

 
SPLAY_MIN

 
SPLAY_MAX

 
SPLAY_FIND

 
SPLAY_LEFT

 
SPLAY_RIGHT

 
SPLAY_FOREACH

 
SPLAY_INIT

 
SPLAY_INSERT

 
SPLAY_REMOVE

 
RB_PROTOTYPE

 
RB_PROTOTYPE_STATIC

 
RB_GENERATE

 
RB_GENERATE_STATIC

 
RB_ENTRY

 
RB_HEAD

 
RB_INITIALIZER

 
RB_ROOT

 
RB_EMPTY

 
RB_NEXT

 
RB_PREV

 
RB_MIN

 
RB_MAX

 
RB_FIND

 
RB_NFIND

 
RB_LEFT

 
RB_RIGHT

 
RB_PARENT

 
RB_FOREACH

 
RB_FOREACH_REVERSE

 
RB_INIT

 
RB_INSERT

 
RB_REMOVE

 - implementations of splay and red-black trees

 

SYNOPSIS

DESCRIPTION

In the macro definitions, Fa TYPE is the name tag of a user defined structure that must contain a field of type Vt SPLAY_ENTRY , or Vt RB_ENTRY , named Fa ENTRYNAME . The argument Fa HEADNAME is the name tag of a user defined structure that must be declared using the macros SPLAY_HEAD (,);
or RB_HEAD (.);
The argument Fa NAME has to be a unique name prefix for every tree that is defined.

The function prototypes are declared with SPLAY_PROTOTYPE (,);
RB_PROTOTYPE (,);
or RB_PROTOTYPE_STATIC (.);
The function bodies are generated with SPLAY_GENERATE (,);
RB_GENERATE (,);
or RB_GENERATE_STATIC (.);
See the examples below for further explanation of how these macros are used.  

SPLAY TREES

This has the benefit that request locality causes faster lookups as the requested nodes move to the top of the tree. On the other hand, every lookup causes memory writes.

The Balance Theorem bounds the total access time for m operations and n inserts on an initially empty tree as O (lp]m + nrp]lg n .);
The amortized cost for a sequence of m accesses to a splay tree is O (lg n .);

A splay tree is headed by a structure defined by the SPLAY_HEAD ();
macro. A structure is declared as follows:

SPLAY_HEAD (HEADNAME TYPE);
head

where Fa HEADNAME is the name of the structure to be defined, and struct Fa TYPE is the type of the elements to be inserted into the tree.

The SPLAY_ENTRY ();
macro declares a structure that allows elements to be connected in the tree.

In order to use the functions that manipulate the tree structure, their prototypes need to be declared with the SPLAY_PROTOTYPE ();
macro, where Fa NAME is a unique identifier for this particular tree. The Fa TYPE argument is the type of the structure that is being managed by the tree. The Fa FIELD argument is the name of the element defined by SPLAY_ENTRY (.);

The function bodies are generated with the SPLAY_GENERATE ();
macro. It takes the same arguments as the SPLAY_PROTOTYPE ();
macro, but should be used only once.

Finally, the Fa CMP argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of type Vt struct TYPE * . If the first argument is smaller than the second, the function returns a value smaller than zero. If they are equal, the function returns zero. Otherwise, it should return a value greater than zero. The compare function defines the order of the tree elements.

The SPLAY_INIT ();
macro initializes the tree referenced by Fa head .

The splay tree can also be initialized statically by using the SPLAY_INITIALIZER ();
macro like this:

SPLAY_HEAD (HEADNAME TYPE);
head = SPLAY_INITIALIZER (&head ;);

The SPLAY_INSERT ();
macro inserts the new element Fa elm into the tree.

The SPLAY_REMOVE ();
macro removes the element Fa elm from the tree pointed by Fa head .

The SPLAY_FIND ();
macro can be used to find a particular element in the tree.

struct TYPE find, *res;
find.key = 30;
res = SPLAY_FIND(NAME, head, &find);

The SPLAY_ROOT (,);
SPLAY_MIN (,);
SPLAY_MAX (,);
and SPLAY_NEXT ();
macros can be used to traverse the tree:

for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))

Or, for simplicity, one can use the SPLAY_FOREACH ();
macro:

SPLAY_FOREACH (np NAME head);

The SPLAY_EMPTY ();
macro should be used to check whether a splay tree is empty.  

RED-BLACK TREES

1. Every search path from the root to a leaf consists of the same number of black nodes.
2. Each red node (except for the root) has a black parent.
3. Each leaf node is black.

Every operation on a red-black tree is bounded as O (lg n .);
The maximum height of a red-black tree is 2lg (n + 1 .);

A red-black tree is headed by a structure defined by the RB_HEAD ();
macro. A structure is declared as follows:

RB_HEAD (HEADNAME TYPE);
head

where Fa HEADNAME is the name of the structure to be defined, and struct Fa TYPE is the type of the elements to be inserted into the tree.

The RB_ENTRY ();
macro declares a structure that allows elements to be connected in the tree.

In order to use the functions that manipulate the tree structure, their prototypes need to be declared with the RB_PROTOTYPE ();
or RB_PROTOTYPE_STATIC ();
macro, where Fa NAME is a unique identifier for this particular tree. The Fa TYPE argument is the type of the structure that is being managed by the tree. The Fa FIELD argument is the name of the element defined by RB_ENTRY (.);

The function bodies are generated with the RB_GENERATE ();
or RB_GENERATE_STATIC ();
macro. These macros take the same arguments as the RB_PROTOTYPE ();
and RB_PROTOTYPE_STATIC ();
macros, but should be used only once.

Finally, the Fa CMP argument is the name of a function used to compare tree noded with each other. The function takes two arguments of type Vt struct TYPE * . If the first argument is smaller than the second, the function returns a value smaller than zero. If they are equal, the function returns zero. Otherwise, it should return a value greater than zero. The compare function defines the order of the tree elements.

The RB_INIT ();
macro initializes the tree referenced by Fa head .

The red-black tree can also be initialized statically by using the RB_INITIALIZER ();
macro like this:

RB_HEAD (HEADNAME TYPE);
head = RB_INITIALIZER (&head ;);

The RB_INSERT ();
macro inserts the new element Fa elm into the tree.

The RB_REMOVE ();
macro removes the element Fa elm from the tree pointed by Fa head .

The RB_FIND ();
and RB_NFIND ();
macros can be used to find a particular element in the tree.

struct TYPE find, *res;
find.key = 30;
res = RB_FIND(NAME, head, &find);

The RB_ROOT (,);
RB_MIN (,);
RB_MAX (,);
RB_NEXT (,);
and RB_PREV ();
macros can be used to traverse the tree:

"for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"

Or, for simplicity, one can use the RB_FOREACH ();
or RB_FOREACH_REVERSE ();
macro:

RB_FOREACH (np NAME head);

The RB_EMPTY ();
macro should be used to check whether a red-black tree is empty.  

NOTES

SPLAY_FOREACH(var, NAME, head) {
        SPLAY_REMOVE(NAME, head, var);
        free(var);
}
free(head);

Since var is freed, the FOREACH ();
macro refers to a pointer that may have been reallocated already. Proper code needs a second variable.

for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
        nxt = SPLAY_NEXT(NAME, head, var);
        SPLAY_REMOVE(NAME, head, var);
        free(var);
}

Both RB_INSERT ();
and SPLAY_INSERT ();
return NULL if the element was inserted in the tree successfully, otherwise they return a pointer to the element with the colliding key.

Accordingly, RB_REMOVE ();
and SPLAY_REMOVE ();
return the pointer to the removed element otherwise they return NULL to indicate an error.  

AUTHORS

Index

NAME

SYNOPSIS

DESCRIPTION

SPLAY TREES

RED-BLACK TREES

NOTES

AUTHORS

Партнёры:

Хостинг: