Lines Matching defs:left
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.
68 * left and right indices. The implementation is written as if it only
69 * dealt with left handed manipulations. By changing the value assigned
70 * to "left", the code also works for right handed trees. The
73 * int left; // 0 when dealing with left children,
76 * int left_heavy; // -1 when left subtree is taller at some node,
79 * int right; // will be the opposite of left (0 or 1)
82 * int direction; // 0 for "<" (ie. left child); 1 for ">" (right)
111 * left and right children when examining a tree. C "if()" statements
124 * towards the left). At any given node we do one of 2 things:
126 * - If there is a left child, go to it, then to it's rightmost descendant.
136 avl_walk(avl_tree_t *tree, void *oldnode, int left)
140 int right = 1 - left;
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];
162 * Otherwise, return thru left children as far as we can.
296 * The code is written as if handling left rotations, right rotations are
297 * symmetric and handled by swapping values of variables right/left[_heavy]
305 int left = !(balance < 0); /* when balance = -2, left will be 0 */
306 int right = 1 - left;
310 avl_node_t *child = node->avl_child[left];
320 * case 1 : node is overly left heavy, the left child is balanced or
321 * also left heavy. This requires the following rotation.
350 * If child used to be left heavy (now balanced) we reduced
356 * move "cright" to be node's left child
359 node->avl_child[left] = cright;
362 AVL_SETCHILD(cright, left);
389 * case 2 : When node is left heavy, but child is right heavy we use
416 * if gchild was right_heavy, then child is now left heavy
421 gleft = gchild->avl_child[left];
425 * move gright to left child of node and
429 node->avl_child[left] = gright;
432 AVL_SETCHILD(gright, left);
442 * move child to left child of gchild and
449 gchild->avl_child[left] = child;
452 AVL_SETCHILD(child, left);
686 int left;
702 * is right heavy, otherwise the left neighbor. This reduces the
711 left = avl_balance2child[old_balance + 1];
712 right = 1 - left;
716 * (down 1 left, as far as possible right)
718 for (node = delete->avl_child[left];
730 if (node->avl_child[left] == node)
731 node->avl_child[left] = &tmp;
738 AVL_SETPARENT(node->avl_child[left], node);
1040 * If here, we moved to a left child. It may have one