Lines Matching full:tree

1 .\"	$OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
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
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
341 into the tree.
347 from the tree pointed by
352 macro can be used to find a particular element in the tree.
365 macros can be used to traverse the tree:
379 macro should be used to check whether a splay tree is empty.
383 Each tree node has an associated rank.
386 Rank differences are stored in each tree node.
393 better balance in the resulting tree.
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
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.
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
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
573 macros can be used to traverse the tree:
590 traverse the tree referenced by head
611 macro should be used to check whether a rank-balanced tree is empty.
617 in the tree.
619 .Nm tree
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.
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
674 To maintain the sum of the values in the tree, each element maintains
676 Lastly, the internal structure of the tree is printed.
680 #include <sys/tree.h>
758 Trying to free a tree in the following way is a common error:
787 if the element was inserted in the tree successfully, otherwise they
812 The tree macros first appeared in
815 The author of the tree macros is