filebench/common/fb_avl.c

35  * any given node, the left and right subtrees are allowed to differ in height
63  *      - The left/right children pointers of a node are in an array.
65  *	  left and right indices.  The implementation is written as if it only
67  *	  to "left", the code also works for right handed trees.  The
71  *				// 1 for dealing with right children
74  *				// +1 when right subtree is taller
76  *		int right;	// will be the opposite of left (0 or 1)
79  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
99  * left and right children when examining a tree.  C "if()" statements
116  * - otherwise we return thru parent nodes until we've come from a right child.
127 	int right = 1 - left;
141 	 * the way right.
145 		    node->avl_child[right] != NULL;
146 		    node = node->avl_child[right])
157 			if (was_child == right)
287  * The code is written as if handling left rotations, right rotations are
288  * symmetric and handled by swapping values of variables right/left[_heavy]
297 	int right = 1 - left;
344 		child_bal += right_heavy; /* adjust towards right */
349 		cright = child->avl_child[right];
357 		 * move node to be child's right child
359 		child->avl_child[right] = node;
361 		AVL_SETCHILD(node, right);
380 	 * case 2 : When node is left heavy, but child is right heavy we use
411 	gchild = child->avl_child[right];
413 	gright = gchild->avl_child[right];
418 	 * move gleft to right child of node
426 	child->avl_child[right] = gleft;
429 		AVL_SETCHILD(gleft, right);
435 	 * move node to right child of gchild and
445 	gchild->avl_child[right] = node;
448 	AVL_SETCHILD(node, right);
662 	int right;
680 	 * is right heavy, otherwise the left neighbor. This reduces the
690 		right = 1 - left;
694 		 * (down 1 left, as far as possible right)
697 		    node->avl_child[right] != NULL;
698 		    node = node->avl_child[right])
717 		AVL_SETPARENT(node->avl_child[right], node);
967 	 * Initial calls go to the first node or it's right descendant.
1014 	 * If we just did a right child or there isn't one, go up to parent.
1023 	 * Do parent's right child, then leftmost descendent.
1033 	 * child on the right (when balance == +1).