|
NAMESPLAY_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_PROTOTYPE_INSERT ,
RB_PROTOTYPE_INSERT_COLOR ,
RB_PROTOTYPE_REMOVE ,
RB_PROTOTYPE_REMOVE_COLOR ,
RB_PROTOTYPE_FIND ,
RB_PROTOTYPE_NFIND ,
RB_PROTOTYPE_NEXT ,
RB_PROTOTYPE_PREV ,
RB_PROTOTYPE_MINMAX ,
RB_PROTOTYPE_REINSERT ,
RB_GENERATE ,
RB_GENERATE_STATIC ,
RB_GENERATE_INSERT ,
RB_GENERATE_INSERT_COLOR ,
RB_GENERATE_REMOVE ,
RB_GENERATE_REMOVE_COLOR ,
RB_GENERATE_FIND ,
RB_GENERATE_NFIND ,
RB_GENERATE_NEXT ,
RB_GENERATE_PREV ,
RB_GENERATE_MINMAX ,
RB_GENERATE_REINSERT ,
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_FROM ,
RB_FOREACH_SAFE ,
RB_FOREACH_REVERSE ,
RB_FOREACH_REVERSE_FROM ,
RB_FOREACH_REVERSE_SAFE ,
RB_INIT , RB_INSERT ,
RB_REMOVE , RB_REINSERT
—
implementations of splay and rank-balanced (wavl) trees
SYNOPSIS#include <sys/tree.h>
struct TYPE *
bool
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
void
struct TYPE *
struct TYPE *
struct TYPE *
bool
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
struct TYPE *
void
struct TYPE *
struct TYPE *
struct TYPE *
DESCRIPTIONThese macros define data structures for different types of trees: splay trees and rank-balanced (wavl) trees.In the macro definitions, TYPE is the name
tag of a user defined structure that must contain a field of type
SPLAY_ENTRY, or RB_ENTRY, named
ENTRYNAME. The argument HEADNAME
is the name tag of a user defined structure that must be declared using the
macros The function prototypes are declared with
SPLAY TREESA 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
m operations and n inserts on an
initially empty tree as A splay tree is headed by a structure defined by the
SPLAY_HEAD (HEADNAME,
TYPE) head;where HEADNAME is the name of the structure to be defined, and struct TYPE is the type of the elements to be inserted into the tree. The In order to use the functions that manipulate the tree structure,
their prototypes need to be declared with the
The function bodies are generated with the
Finally, the CMP argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of type 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 The splay tree can also be initialized statically by using the
SPLAY_HEAD (HEADNAME,
TYPE) head =
SPLAY_INITIALIZER (&head);The The The struct TYPE find, *res; find.key = 30; res = SPLAY_FIND(NAME, head, &find); The for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) Or, for simplicity, one can use the
SPLAY_FOREACH (np,
NAME, head)The RANK-BALANCED TREESRank-balanced (RB) trees are a framework for defining height-balanced binary search trees, including AVL and red-black trees. Each tree node has an associated rank. Balance conditions are expressed by conditions on the differences in rank between any node and its children. Rank differences are stored in each tree node.The balance conditions implemented by the RB macros lead to weak AVL (wavl) trees, which combine the best aspects of AVL and red-black trees. Wavl trees rebalance after an insertion in the same way AVL trees do, with the same worst-case time as red-black trees offer, and with better balance in the resulting tree. Wavl trees rebalance after a removal in a way that requires less restructuring, in the worst case, than either AVL or red-black trees do. Removals can lead to a tree almost as unbalanced as a red-black tree; insertions lead to a tree becoming as balanced as an AVL tree. A rank-balanced tree is headed by a structure defined by the
RB_HEAD (HEADNAME,
TYPE) head;where HEADNAME is the name of the structure to be defined, and struct TYPE is the type of the elements to be inserted into the tree. The In order to use the functions that manipulate the tree structure,
their prototypes need to be declared with the
The function bodies are generated with the
Finally, the CMP argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of type 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 The rank-balanced tree can also be initialized statically by using
the RB_HEAD (HEADNAME,
TYPE) head =
RB_INITIALIZER (&head);The The The struct TYPE find, *res; find.key = 30; res = RB_FIND(NAME, head, &find); The for (np = RB_MIN(NAME, &head); np
!= NULL; np = RB_NEXT(NAME, &head, np)) Or, for simplicity, one can use the
RB_FOREACH (np,
NAME, head)The macros Both The The EXAMPLESThe following example demonstrates how to declare a rank-balanced tree holding integers. Values are inserted into it and the contents of the tree are printed in order. Lastly, the internal structure of the tree is printed.#include <sys/tree.h> #include <err.h> #include <stdio.h> #include <stdlib.h> struct node { RB_ENTRY(node) entry; int i; }; int intcmp(struct node *e1, struct node *e2) { return (e1->i < e2->i ? -1 : e1->i > e2->i); } RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); RB_GENERATE(inttree, node, entry, intcmp) int testdata[] = { 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, 7, 11, 14 }; void print_tree(struct node *n) { struct node *left, *right; if (n == NULL) { printf("nil"); return; } left = RB_LEFT(n, entry); right = RB_RIGHT(n, entry); if (left == NULL && right == NULL) printf("%d", n->i); else { printf("%d(", n->i); print_tree(left); printf(","); print_tree(right); printf(")"); } } int main(void) { int i; struct node *n; for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { if ((n = malloc(sizeof(struct node))) == NULL) err(1, NULL); n->i = testdata[i]; RB_INSERT(inttree, &head, n); } RB_FOREACH(n, inttree, &head) { printf("%d\n", n->i); } print_tree(RB_ROOT(&head)); printf("\n"); return (0); } NOTESTrying 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 var is freed, the
for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { nxt = SPLAY_NEXT(NAME, head, var); SPLAY_REMOVE(NAME, head, var); free(var); } Both Accordingly, SEE ALSOarb(3), queue(3)Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan, Rank-Balanced Trees, ACM Transactions on Algorithms, 4, 11, http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf, June 2015. HISTORYThe tree macros first appeared in FreeBSD 4.6.AUTHORSThe author of the tree macros is Niels Provos.
Visit the GSP FreeBSD Man Page Interface. |