Lines Matching refs:tree
32 * AVL - generic AVL tree implementation for kernel use
36 * Here is a very brief overview. An AVL tree is a binary search tree that is
41 * This relaxation from a perfectly balanced binary tree allows doing
42 * insertion and deletion relatively efficiently. Searching the tree is
45 * The key to insertion and deletion is a set of tree manipulations called
63 * there is no recursion stack present to move "up" in the tree,
85 * allows using half as much code (and hence cache footprint) for tree
89 * adjacent to where a new value would be inserted in the tree. The value
110 * Code that deals with binary tree data structures will randomly use
111 * left and right children when examining a tree. C "if()" statements
136 avl_walk(avl_tree_t *tree, void *oldnode, int left)
138 size_t off = tree->avl_offset;
145 * nowhere to walk to if tree is empty
179 * Return the lowest valued node in a tree or NULL.
180 * (leftmost child from root of tree)
183 avl_first(avl_tree_t *tree)
187 size_t off = tree->avl_offset;
189 for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
198 * Return the highest valued node in a tree or NULL.
199 * (rightmost child from root of tree)
202 avl_last(avl_tree_t *tree)
206 size_t off = tree->avl_offset;
208 for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
223 * "void *" of the found tree node
226 avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
231 size_t off = tree->avl_offset;
234 ASSERT(tree->avl_root == NULL);
241 return (avl_walk(tree, data, direction));
247 * simple binary tree search.
250 * NULL: the value is not in the AVL tree
252 * "void *" of the found tree node
255 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where)
261 size_t off = tree->avl_offset;
263 for (node = tree->avl_root; node != NULL;
268 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
303 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
351 * the height of this sub-tree -- used in "return...;" below
382 tree->avl_root = child;
465 tree->avl_root = gchild;
467 return (1); /* the new tree is always shorter */
472 * Insert a new node into an AVL tree at the specified (from avl_find()) place.
474 * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
478 * After the node is inserted, a single rotation further up the tree may
482 avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
489 size_t off = tree->avl_offset;
491 ASSERT(tree);
499 * First, add the node to the tree at the indicated position.
501 ++tree->avl_numnodes;
513 ASSERT(tree->avl_root == NULL);
514 tree->avl_root = node;
517 * Now, back up the tree modifying the balance of all nodes above the
519 * need to do a rotation. If we back out of the tree we are done.
554 * perform a rotation to fix the tree and return
556 (void) avl_rotation(tree, node, new_balance);
560 * Insert "new_data" in "tree" in the given "direction" either after or
563 * Insertions can only be done at empty leaf points in the tree, therefore
566 * every other node in the tree is a leaf, this always works.
573 avl_tree_t *tree,
584 ASSERT(tree != NULL);
593 node = AVL_DATA2NODE(here, tree->avl_offset);
596 diff = tree->avl_compar(new_data, here);
607 diff = tree->avl_compar(new_data,
608 AVL_NODE2DATA(node, tree->avl_offset));
616 diff = tree->avl_compar(new_data,
617 AVL_NODE2DATA(node, tree->avl_offset));
625 avl_insert(tree, new_data, AVL_MKINDEX(node, child));
629 * Add a new node to an AVL tree.
632 avl_add(avl_tree_t *tree, void *new_node)
644 if (avl_find(tree, new_node, &where) != NULL)
651 avl_insert(tree, new_node, where);
655 * Delete a node from the AVL tree. Deletion is similar to insertion, but
668 * handled by temporarily swapping (d) and (c) in the tree and then using
671 * Secondly, an interior deletion from a deep tree may require more than one
672 * rotation to fix the balance. This is handled by moving up the tree through
678 avl_remove(avl_tree_t *tree, void *data)
689 size_t off = tree->avl_offset;
691 ASSERT(tree);
701 * As an optimization, we choose the greater neighbor if the tree
725 * move 'node' to delete's spot in the tree
737 tree->avl_root = node;
756 * be easily removed from the tree.
758 ASSERT(tree->avl_numnodes > 0);
759 --tree->avl_numnodes;
775 tree->avl_root = node;
788 * Move up the tree and adjust the balance
814 * of the sub-tree we have finished adjusting.
818 else if (!avl_rotation(tree, node, new_balance))
823 #define AVL_REINSERT(tree, obj) \
824 avl_remove((tree), (obj)); \
825 avl_add((tree), (obj))
900 * initialize a new AVL tree
903 avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
906 ASSERT(tree);
914 tree->avl_compar = compar;
915 tree->avl_root = NULL;
916 tree->avl_numnodes = 0;
917 tree->avl_size = size;
918 tree->avl_offset = offset;
922 * Delete a tree.
926 avl_destroy(avl_tree_t *tree)
928 ASSERT(tree);
929 ASSERT(tree->avl_numnodes == 0);
930 ASSERT(tree->avl_root == NULL);
935 * Return the number of nodes in an AVL tree.
938 avl_numnodes(avl_tree_t *tree)
940 ASSERT(tree);
941 return (tree->avl_numnodes);
945 avl_is_empty(avl_tree_t *tree)
947 ASSERT(tree);
948 return (tree->avl_numnodes == 0);
954 * Post-order tree walk used to visit all tree nodes and destroy the tree
955 * in post order. This is used for destroying a tree without paying any cost
963 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
965 * avl_destroy(tree);
970 * On input, a cookie value of CHILDBIT indicates the tree is done.
973 avl_destroy_nodes(avl_tree_t *tree, void **cookie)
979 size_t off = tree->avl_offset;
985 first = avl_first(tree);
988 * deal with an empty tree
1005 if (tree->avl_root != NULL) {
1006 ASSERT(tree->avl_numnodes == 1);
1007 tree->avl_root = NULL;
1008 tree->avl_numnodes = 0;
1014 * Remove the child pointer we just visited from the parent and tree.
1018 ASSERT(tree->avl_numnodes > 1);
1019 --tree->avl_numnodes;
1057 ASSERT(node == tree->avl_root);