Lines Matching +full:in +full:- +full:tree
1 .\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
6 .\" Redistribution and use in source and binary forms, with or without
11 .\" 2. Redistributions in binary form must reproduce the above copyright
12 .\" notice, this list of conditions and the following disclaimer in the
23 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
27 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
32 .Dt TREE 3
105 .Nd "implementations of splay and rank-balanced (wavl) trees"
107 .In sys/tree.h
211 splay trees and rank-balanced (wavl) trees.
213 In the macro definitions,
230 has to be a unique name prefix for every tree that is defined.
244 A splay tree is a self-organizing data structure.
245 Every operation on the tree causes a splay to happen.
247 node to the root of the tree and partly rebalances it.
250 the requested nodes move to the top of the tree.
257 inserts on an initially empty tree as
262 accesses to a splay tree is
265 A splay tree is headed by a structure defined by the
270 .Bd -ragged -offset indent
279 is the type of the elements to be inserted into the tree.
283 macro declares a structure that allows elements to be connected in the tree.
285 In order to use the functions that manipulate the tree structure,
291 is a unique identifier for this particular tree.
295 by the tree.
311 argument is the name of a function used to compare tree nodes
320 function defines the order of the tree elements.
324 macro initializes the tree referenced by
327 The splay tree can also be initialized statically by using the
330 .Bd -ragged -offset indent
341 into the tree.
347 from the tree pointed by
352 macro can be used to find a particular element in the tree.
353 .Bd -literal -offset indent
365 macros can be used to traverse the tree:
366 .Bd -literal -offset indent
373 .Bd -ragged -offset indent
379 macro should be used to check whether a splay tree is empty.
380 .Sh RANK-BALANCED TREES
381 Rank-balanced (RB) trees are a framework for defining height-balanced
382 binary search trees, including AVL and red-black trees.
383 Each tree node has an associated rank.
384 Balance conditions are expressed by conditions on the differences in
386 Rank differences are stored in each tree node.
389 (wavl) trees, which combine the best aspects of AVL and red-black
391 Wavl trees rebalance after an insertion in the same way AVL trees do,
392 with the same worst-case time as red-black trees offer, and with
393 better balance in the resulting tree.
394 Wavl trees rebalance after a removal in a way that requires less
395 restructuring, in the worst case, than either AVL or red-black trees
397 Removals can lead to a tree almost as unbalanced as a red-black
398 tree; insertions lead to a tree becoming as balanced as an AVL tree.
400 A rank-balanced tree is headed by a structure defined by the
405 .Bd -ragged -offset indent
414 is the type of the elements to be inserted into the tree.
418 macro declares a structure that allows elements to be connected in the tree.
420 In order to use the functions that manipulate the tree structure,
428 is a unique identifier for this particular tree.
432 by the tree.
449 in case not all functions are required.
489 argument is the name of a function used to compare tree nodes
498 function defines the order of the tree elements.
502 macro initializes the tree referenced by
505 The rank-balanced tree can also be initialized statically by using the
508 .Bd -ragged -offset indent
519 into the tree.
525 into the tree immediately after a given element.
531 into the tree immediately before a given element.
537 from the tree pointed by
544 macros can be used to find a particular element in the tree.
548 macro returns the element in the tree equal to the provided
559 .Bd -literal -offset indent
573 macros can be used to traverse the tree:
582 .Bd -ragged -offset indent
590 traverse the tree referenced by head
591 in a forward or reverse direction respectively,
592 assigning each element in turn to np.
603 in a forward or reverse direction respectively.
611 macro should be used to check whether a rank-balanced tree is empty.
617 in the tree.
619 .Nm tree
620 is modified in a way that affects comparison, such as by modifying
629 in the tree.
635 from the tree, it is invoked for every element in the tree that is the
636 root of an altered subtree, working from the bottom of the tree up to
638 It is typically used to maintain some associative accumulation of tree
645 in the tree.
649 is defined, then when an element is inserted or removed from the tree,
650 it is invoked for every element in the tree that is the root of an
651 altered subtree, working from the bottom of the tree up toward the
653 element and so working further up the tree would change nothing.
654 It is typically used to maintain some associative accumulation of tree
661 and its ancestors in the tree.
664 is defined by the RB user, then when an element in the
665 tree is changed, without changing the order of items in the tree,
667 augmentation state of the tree as if the element had been removed and
670 The following example demonstrates how to declare a rank-balanced tree
672 Values are inserted into it and the contents of the tree are printed
673 in order.
674 To maintain the sum of the values in the tree, each element maintains
676 Lastly, the internal structure of the tree is printed.
677 .Bd -literal -offset 3n
680 #include <sys/tree.h>
693 return (e1->i < e2->i ? -1 : e1->i > e2->i);
699 e->sum = e->i;
701 e->sum += RB_LEFT(e, entry)->sum;
703 e->sum += RB_RIGHT(e, entry)->sum;
726 printf("%d", n->i);
728 printf("%d(", n->i);
745 n->i = testdata[i];
750 printf("%d\en", n->i);
753 printf("\enSum of values = %d\en", RB_ROOT(&head)->sum);
758 Trying to free a tree in the following way is a common error:
759 .Bd -literal -offset indent
773 .Bd -literal -offset indent
787 if the element was inserted in the tree successfully, otherwise they
804 .%T "Rank-Balanced Trees"
805 .%U "http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf"
812 The tree macros first appeared in
815 The author of the tree macros is