common/avl/avl.c

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
70  *	  to "left", the code also works for right handed trees.  The
74  *				// 1 for dealing with right children
77  *				// +1 when right subtree is taller
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
128  * - otherwise we return through parent nodes until we've come from a right
140 	int right = 1 - left;
154 	 * the way right.
158 		    node->avl_child[right] != NULL;
159 		    node = node->avl_child[right])
170 			if (was_child == right)
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]
306 	int right = 1 - left;
353 		child_bal += right_heavy; /* adjust towards right */
358 		cright = child->avl_child[right];
366 		 * move node to be child's right child
368 		child->avl_child[right] = node;
370 		AVL_SETCHILD(node, right);
389 	 * case 2 : When node is left heavy, but child is right heavy we use
420 	gchild = child->avl_child[right];
422 	gright = gchild->avl_child[right];
427 	 * move gleft to right child of node
435 	child->avl_child[right] = gleft;
438 		AVL_SETCHILD(gleft, right);
444 	 * move node to right child of gchild and
454 	gchild->avl_child[right] = node;
457 	AVL_SETCHILD(node, right);
687 	int right;
702 	 * is right heavy, otherwise the left neighbor. This reduces the
712 		right = 1 - left;
716 		 * (down 1 left, as far as possible right)
719 		    node->avl_child[right] != NULL;
720 		    node = node->avl_child[right])
739 		AVL_SETPARENT(node->avl_child[right], node);
982 	 * Initial calls go to the first node or it's right descendant.
1022 	 * If we just did a right child or there isn't one, go up to parent.
1031 	 * Do parent's right child, then leftmost descendent.
1041 	 * child on the right (when balance == +1).