Manpages - tree.3bsd

(See

for include usage.)

These macros define data structures for different types of trees: splay trees and red-black trees.

In the macro definitions,

is the name tag of a user defined structure that must contain a field of type

named

The argument

is the name tag of a user defined structure that must be declared using the macros

The argument

has to be a unique name prefix for every tree that is defined.

The function prototypes are declared with

The function bodies are generated with

See the examples below for further explanation of how these macros are used.

A splay tree is a self-organizing data structure. Every operation on the tree causes a splay to happen. The splay moves the requested node to the root of the tree and partly rebalances it.

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

operations and

inserts on an initially empty tree as

The amortized cost for a sequence of

accesses to a splay tree is

A splay tree is headed by a structure defined by the

macro. A structure is declared as follows:

where

is the name of the structure to be defined, and struct

is the type of the elements to be inserted into the tree.

The

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

macro, where

is a unique identifier for this particular tree. The

argument is the type of the structure that is being managed by the tree. The

argument is the name of the element defined by

The function bodies are generated with the

macro. It takes the same arguments as the

macro, but should be used only once.

Finally, the

argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of 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

macro initializes the tree referenced by

The splay tree can also be initialized statically by using the

macro like this:

The

macro inserts the new element

into the tree.

The

macro removes the element

from the tree pointed by

The

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

and

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

macro:

The

macro should be used to check whether a splay tree is empty.

A red-black tree is a binary search tree with the node color as an extra attribute. It fulfills a set of conditions:

Every search path from the root to a leaf consists of the same number of black nodes.

Each red node (except for the root) has a black parent.

Each leaf node is black.

Every operation on a red-black tree is bounded as

The maximum height of a red-black tree is

A red-black tree is headed by a structure defined by the

macro. A structure is declared as follows:

where

is the name of the structure to be defined, and struct

is the type of the elements to be inserted into the tree.

The

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

macro, where

is a unique identifier for this particular tree. The

argument is the type of the structure that is being managed by the tree. The

argument is the name of the element defined by

The function bodies are generated with the

macro. These macros take the same arguments as the

and

macros, but should be used only once.

Finally, the

argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of type

The

macro initializes the tree referenced by

The red-black tree can also be initialized statically by using the

macro like this:

The

macro inserts the new element

into the tree.

The

macro removes the element

from the tree pointed by

The

and

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

and

macros can be used to traverse the tree:

Or, for simplicity, one can use the

macro:

The

macro should be used to check whether a red-black tree is empty.

Trying to free a tree in the following way is a common error:

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

Since

is freed, the

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

and

return

if the element was inserted in the tree successfully, otherwise they return a pointer to the element with the colliding key.

Accordingly,

and

return the pointer to the removed element otherwise they return

to indicate an error.

The author of the tree macros is