Lines Matching defs:node
38 * any given node, the left and right subtrees are allowed to differ in height
66 * - The left/right children pointers of a node are in an array.
76 * int left_heavy; // -1 when left subtree is taller at some node,
91 * pointer) is set to indicate if that the new node has a value greater
123 * Walk from one node to the previous valued node (ie. an infix walk
124 * towards the left). At any given node we do one of 2 things:
133 * otherwise next node
139 avl_node_t *node = AVL_DATA2NODE(oldnode, off);
147 if (node == NULL)
151 * Visit the previous valued node. There are two possibilities:
153 * If this node has a left child, go down one left, then all
156 if (node->avl_child[left] != NULL) {
157 for (node = node->avl_child[left];
158 node->avl_child[right] != NULL;
159 node = node->avl_child[right])
166 was_child = AVL_XCHILD(node);
167 node = AVL_XPARENT(node);
168 if (node == NULL)
175 return (AVL_NODE2DATA(node, off));
179 * Return the lowest valued node in a tree or NULL.
185 avl_node_t *node;
189 for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
190 prev = node;
198 * Return the highest valued node in a tree or NULL.
204 avl_node_t *node;
208 for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
209 prev = node;
217 * Access the node immediately before or after an insertion point.
222 * NULL: no node in the given direction
223 * "void *" of the found tree node
229 avl_node_t *node = AVL_INDEX2NODE(where);
233 if (node == NULL) {
237 data = AVL_NODE2DATA(node, off);
246 * Search for the node which contains "value". The algorithm is a
252 * "void *" of the found tree node
257 avl_node_t *node;
263 for (node = tree->avl_root; node != NULL;
264 node = node->avl_child[child]) {
266 prev = node;
268 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
275 return (AVL_NODE2DATA(node, off));
299 * On input balance is the "new" balance at "node". This value is either
303 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
309 avl_node_t *parent = AVL_XPARENT(node);
310 avl_node_t *child = node->avl_child[left];
315 int which_child = AVL_XCHILD(node);
320 * case 1 : node is overly left heavy, the left child is balanced or
323 * (node bal:-2)
336 * (node bal:-1 or 0)
356 * move "cright" to be node's left child
359 node->avl_child[left] = cright;
361 AVL_SETPARENT(cright, node);
366 * move node to be child's right child
368 child->avl_child[right] = node;
369 AVL_SETBALANCE(node, -child_bal);
370 AVL_SETCHILD(node, right);
371 AVL_SETPARENT(node, child);
389 * case 2 : When node is left heavy, but child is right heavy we use
392 * (node b:-2)
410 * (child b:?) (node b:?)
425 * move gright to left child of node and
427 * move gleft to right child of node
429 node->avl_child[left] = gright;
431 AVL_SETPARENT(gright, node);
444 * move node to right child of gchild and
454 gchild->avl_child[right] = node;
455 AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));
456 AVL_SETPARENT(node, gchild);
457 AVL_SETCHILD(node, right);
472 * Insert a new node into an AVL tree at the specified (from avl_find()) place.
475 * searches out to the leaf positions. The avl_index_t indicates the node
476 * which will be the parent of the new node.
478 * After the node is inserted, a single rotation further up the tree may
484 avl_node_t *node;
496 node = AVL_DATA2NODE(new_data, off);
499 * First, add the node to the tree at the indicated position.
503 node->avl_child[0] = NULL;
504 node->avl_child[1] = NULL;
506 AVL_SETCHILD(node, which_child);
507 AVL_SETBALANCE(node, 0);
508 AVL_SETPARENT(node, parent);
511 parent->avl_child[which_child] = node;
514 tree->avl_root = node;
523 node = parent;
524 if (node == NULL)
530 old_balance = AVL_XBALANCE(node);
537 AVL_SETBALANCE(node, 0);
548 AVL_SETBALANCE(node, new_balance);
549 parent = AVL_XPARENT(node);
550 which_child = AVL_XCHILD(node);
556 (void) avl_rotation(tree, node, new_balance);
564 * if the given child of the node is already present we move to either
566 * every other node in the tree is a leaf, this always works.
568 * To help developers using this interface, we assert that the new node
578 avl_node_t *node;
590 * If corresponding child of node is not NULL, go to the neighboring
591 * node and reverse the insertion direction.
593 node = AVL_DATA2NODE(here, tree->avl_offset);
602 if (node->avl_child[child] != NULL) {
603 node = node->avl_child[child];
605 while (node->avl_child[child] != NULL) {
608 AVL_NODE2DATA(node, tree->avl_offset));
613 node = node->avl_child[child];
617 AVL_NODE2DATA(node, tree->avl_offset));
623 ASSERT(node->avl_child[child] == NULL);
625 avl_insert(tree, new_data, AVL_MKINDEX(node, child));
629 * Add a new node to an AVL tree.
655 * Delete a node from the AVL tree. Deletion is similar to insertion, but
658 * First, we may be deleting an interior node. Consider the following subtree:
666 * When we are deleting node (d), we find and bring up an adjacent valued leaf
667 * node, say (c), to take the interior node's place. In the code this is
682 avl_node_t *node;
696 * Deletion is easiest with a node that has at most 1 child.
697 * We swap a node with 2 children with a sequentially valued
698 * neighbor node. That node will have at most 1 child. Note this
708 * choose node to swap from whichever side is taller
715 * get to the previous value'd node
718 for (node = delete->avl_child[left];
719 node->avl_child[right] != NULL;
720 node = node->avl_child[right])
724 * create a temp placeholder for 'node'
725 * move 'node' to delete's spot in the tree
727 tmp = *node;
729 *node = *delete;
730 if (node->avl_child[left] == node)
731 node->avl_child[left] = &tmp;
733 parent = AVL_XPARENT(node);
735 parent->avl_child[AVL_XCHILD(node)] = node;
737 tree->avl_root = node;
738 AVL_SETPARENT(node->avl_child[left], node);
739 AVL_SETPARENT(node->avl_child[right], node);
742 * Put tmp where node used to be (just temporary).
755 * Here we know "delete" is at least partially a leaf node. It can
763 node = delete->avl_child[0];
765 node = delete->avl_child[1];
768 * Connect parent directly to node (leaving out delete).
770 if (node != NULL) {
771 AVL_SETPARENT(node, parent);
772 AVL_SETCHILD(node, which_child);
775 tree->avl_root = node;
778 parent->avl_child[which_child] = node;
793 node = parent;
794 old_balance = AVL_XBALANCE(node);
796 parent = AVL_XPARENT(node);
797 which_child = AVL_XCHILD(node);
800 * If a node was in perfect balance but isn't anymore then
805 AVL_SETBALANCE(node, new_balance);
817 AVL_SETBALANCE(node, new_balance);
818 else if (!avl_rotation(tree, node, new_balance))
961 * my_data_t *node;
963 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
964 * free(node);
967 * The cookie is really an avl_node_t to the current node's parent and
975 avl_node_t *node;
982 * Initial calls go to the first node or it's right descendant.
995 node = AVL_DATA2NODE(first, off);
996 parent = AVL_XPARENT(node);
1025 node = parent;
1033 node = parent->avl_child[1];
1034 while (node->avl_child[0] != NULL) {
1035 parent = node;
1036 node = node->avl_child[0];
1044 if (node->avl_child[1] != NULL) {
1045 ASSERT(AVL_XBALANCE(node) == 1);
1046 parent = node;
1047 node = node->avl_child[1];
1048 ASSERT(node->avl_child[0] == NULL &&
1049 node->avl_child[1] == NULL);
1051 ASSERT(AVL_XBALANCE(node) <= 0);
1057 ASSERT(node == tree->avl_root);
1059 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));
1062 return (AVL_NODE2DATA(node, off));