common/avl/avl.c

37  * any given node, the left and right subtrees are allowed to differ in height
65  *      - The left/right children pointers of a node are in an array.
67  *	  left and right indices.  The implementation is written as if it only
69  *	  to "left", the code also works for right handed trees.  The
73  *				// 1 for dealing with right children
76  *				// +1 when right subtree is taller
78  *		int right;	// will be the opposite of left (0 or 1)
81  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
110  * left and right children when examining a tree.  C "if()" statements
127  * - otherwise we return through parent nodes until we've come from a right
139 	int right = 1 - left;
153 	 * the way right.
157 		    node->avl_child[right] != NULL;
158 		    node = node->avl_child[right])
169 			if (was_child == right)
295  * The code is written as if handling left rotations, right rotations are
296  * symmetric and handled by swapping values of variables right/left[_heavy]
305 	int right = 1 - left;
352 		child_bal += right_heavy; /* adjust towards right */
357 		cright = child->avl_child[right];
365 		 * move node to be child's right child
367 		child->avl_child[right] = node;
369 		AVL_SETCHILD(node, right);
388 	 * case 2 : When node is left heavy, but child is right heavy we use
419 	gchild = child->avl_child[right];
421 	gright = gchild->avl_child[right];
426 	 * move gleft to right child of node
434 	child->avl_child[right] = gleft;
437 		AVL_SETCHILD(gleft, right);
443 	 * move node to right child of gchild and
453 	gchild->avl_child[right] = node;
456 	AVL_SETCHILD(node, right);
683 	int right;
698 	 * is right heavy, otherwise the left neighbor. This reduces the
708 		right = 1 - left;
712 		 * (down 1 left, as far as possible right)
715 		    node->avl_child[right] != NULL;
716 		    node = node->avl_child[right])
735 		AVL_SETPARENT(node->avl_child[right], node);
978 	 * Initial calls go to the first node or it's right descendant.
1018 	 * If we just did a right child or there isn't one, go up to parent.
1027 	 * Do parent's right child, then leftmost descendent.
1037 	 * child on the right (when balance == +1).