GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  AVL (3)

NAME

mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines

CONTENTS

Synopsis
Description
Examples
Source
See Also
Diagnostics

SYNOPSIS

#include <u.h> #include <libc.h> #include <avl.h>

typedef struct Avl Avl; struct Avl {
       Avl    *p;           /* parent */
       Avl    *n[2];        /* children */
       int    bal;          /* balance bits */ };

Avl    *avlnext(Avlwalk *walk); Avl    *avlprev(Avlwalk *walk); Avlwalk       *avlwalk(Avltree *tree); void   deleteavl(Avltree *tree, Avl *key, Avl **oldp); void   endwalk(Avlwalk *walk); void   insertavl(Avltree *tree, Avl *new, Avl **oldp); Avl    *lookupavl(Avltree *tree, Avl *key); Avl    *searchavl(Avltree *tree, Avl *key, int neighbor); Avltree       *mkavltree(int(*cmp)(Avl*, Avl*));

DESCRIPTION

An AVL tree is a self-balancing binary search tree. These routines allow creation and maintenance of in-memory AVL trees.

An empty AVL tree is created by calling mkavltree with a comparison function as argument. This function should take two pointers to Avl objects and return -1, 0 or 1 as the first is respectively less than, equal to, or greater than, the second. Insertavl adds a new tree node into tree. If oldp is non-nil upon return, it points to storage for an old node with the same key that may now be freed. Lookupavl returns the tree node that matches key by tree’s comparison function, or nil if none.

Searchavl returns the tree node that matches key by tree’s comparison function, if it exists. If it does not, and neighbor is positive, it returns the nearest node whose key is greater or nil if there is none and, if neighbor is negative, it returns the nearest node whose key is less or nil if there is none. It is an error to set neighbor to values other than -1, 0, or +1.

Deleteavl removes the node matching key from tree; oldp is handled as per insertavl.

Avlwalk returns a pointer to a newly-allocated Avlwalk object. Endwalk frees such an object. Avlnext and avlprev walk the tree associated with walk, returning the next (respectively, previous) tree node in the comparison order defined by the comparison function associated with the tree associated with walk.

EXAMPLES

Intended usage seems to be to make an anonymous Avl the first member of the application’s tree-node structure, then pass these routines tree-node pointers instead of Avl*s.
typedef struct Node {
       Avl;
       uchar  score[VtScoreSize];
       int    type; } Node;

Avltree *tree; Avl *res; Node *np; ...
       res = lookupavl(tree, np);

SOURCE

/usr/local/plan9/src/libavl

SEE ALSO

G. M. Adelson-Velsky, E. M. Landis, ‘‘An algorithm for the organization of information’’, Soviet Mathematics, Vol. 3, pp. 1256—1263.

DIAGNOSTICS

Functions returning pointers return nil on error.
Search for    or go to Top of page |  Section 3 |  Main Index


AVL (3) -->

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.