.TH AVL 3 | |

.SH NAME | |

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

.SH SYNOPSIS | |

.\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i | |

.ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i | |

.EX | |

#include <u.h> | |

#include <libc.h> | |

#include <avl.h> | |

.sp 0.3v | |

typedef struct Avl Avl; | |

struct Avl | |

{ | |

Avl *p; /* parent */ | |

Avl *n[2]; /* children */ | |

int bal; /* balance bits */ | |

}; | |

.sp 0.3v | |

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*)); | |

.EE | |

.SH DESCRIPTION | |

An AVL tree is a self-balancing binary search tree. | |

These routines allow creation and maintenance of in-memory AVL trees. | |

.PP | |

An empty AVL tree is created by calling | |

.I mkavltree | |

with a comparison function as argument. | |

This function should take two pointers to | |

.B Avl | |

objects and return -1, 0 or 1 as the first is | |

respectively less than, | |

equal to, or greater than, | |

the second. | |

.I Insertavl | |

adds a | |

.I new | |

tree node into | |

.IR tree . | |

If | |

.I oldp | |

is non-nil upon return, | |

it points to storage for an old node | |

with the same key that may now be freed. | |

.I Lookupavl | |

returns the | |

.I tree | |

node that matches | |

.I key | |

by | |

.IR tree 's | |

comparison function, | |

or | |

.B nil | |

if none. | |

.PP | |

.I Searchavl | |

returns the | |

.I tree | |

node that matches | |

.I key | |

by | |

.IR tree 's | |

comparison function, if it exists. | |

If it does not, and | |

.I neighbor | |

is positive, it returns the nearest node whose | |

.I key | |

is greater or | |

.B nil | |

if there is none and, if | |

.I neighbor | |

is negative, it returns the nearest node whose | |

.I key | |

is less or | |

.B nil | |

if there is none. | |

It is an error to set | |

.I neighbor | |

to values other than \-1, 0, or +1. | |

.PP | |

.I Deleteavl | |

removes the node matching | |

.I key | |

from | |

.IR tree ; | |

.I oldp | |

is handled as per | |

.IR insertavl . | |

.PP | |

.I Avlwalk | |

returns a pointer to a newly-allocated | |

.B Avlwalk | |

object. | |

.I Endwalk | |

frees such an object. | |

.I Avlnext | |

and | |

.I avlprev | |

walk the tree associated with | |

.IR walk , | |

returning the next | |

(respectively, previous) | |

tree node in the comparison order | |

defined by the comparison function | |

associated with the tree associated with | |

.IR walk . | |

.SH EXAMPLES | |

Intended usage seems to be to make an anonymous | |

.B Avl | |

the first member of the application's tree-node structure, | |

then pass these routines tree-node pointers instead of | |

.BR Avl* s. | |

.IP | |

.EX | |

typedef struct Node { | |

Avl; | |

uchar score[VtScoreSize]; | |

int type; | |

} Node; | |

.sp 0.3v | |

Avltree *tree; | |

Avl *res; | |

Node *np; | |

\fI\&...\fP | |

res = lookupavl(tree, np); | |

.EE | |

.SH SOURCE | |

.B \*9/src/libavl | |

.SH SEE ALSO | |

G. M. Adelson-Velsky, | |

E. M. Landis, | |

``An algorithm for the organization of information'', | |

.IR "Soviet Mathematics" , | |

Vol. 3, pp. 1256—1263. | |

.SH DIAGNOSTICS | |

Functions returning pointers return | |

.B nil | |

on error. |