kernel/util/AVLTreeBase.cpp

72 		while (node->left)
73 			node = node->left;
97 		if (node->left) {
98 			// We have a left subtree, so go to the right-most node.
99 			node = node->left;
103 			// No left subtree: Backtrack our path and stop, where we
109 			} while (node && previous == node->left);
121 		// The next node cannot be in the left subtree.
123 			// We have a right subtree, so go to the left-most node.
125 			while (node->left)
126 				node = node->left;
129 			// took the left branch.
153 			node = node->left;
175 			node = node->left;
227 				node = node->left;
272 	AVLTreeNode* left = node->left;
274 	*nodeP = left;
276 	left->parent = node->parent;
277 	node->left = left->right;
278 	if (left->right)
279 		left->right->parent = node;
280 	left->right = node;
281 	node->parent = left;
285 	if (left->balance_factor >= 0)
288 		node->balance_factor += 1 - left->balance_factor;
290 	// former left
292 		left->balance_factor++;
294 		left->balance_factor += node->balance_factor + 1;
308 	node->right = right->left;
309 	if (right->left)
310 		right->left->parent = node;
311 	right->left = node;
333 		// tree is left heavy
334 		AVLTreeNode** left = &(*node)->left;
335 		if ((*left)->balance_factor == LEFT) {
336 			// left left heavy
339 			// left right heavy
340 			_RotateLeft(left);
363 			// right left heavy
382 		bool			left;
398 				top->left = true;
399 				node = &(*node)->left;
401 				top->left = false;
410 	nodeToInsert->left = NULL;
425 		if (top->left) {
426 			// left
456 			// right left heavy
473 		// tree is left heavy
474 		AVLTreeNode** left = &(*node)->left;
475 		if ((*left)->balance_factor == LEFT) {
476 			// left left heavy
478 		} else if ((*left)->balance_factor == BALANCED) {
479 			// left none heavy
483 			// left right heavy
484 			_RotateLeft(left);
509 	// the found node might have a left child: replace the node with the
512 	AVLTreeNode* left = (*node)->left;
513 	if (left)
514 		left->parent = (*node)->parent;
515 	*node = left;
516 	(*foundNode)->left = NULL;
540 	bool isLeft = (parent && parent->left == node);
542 		= (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
546 	if (node->left && node->right) {
548 		result = _RemoveRightMostChild(&node->left, &replace);
550 		replace->left = node->left;
552 		if (node->left)	// check necessary, if node->left == replace
553 			node->left->parent = replace;
562 	} else if (node->left) {
563 		// node has only left child
564 		replace = node->left;
586 		isLeft = (parent && parent->left == node);
587 		nodeP = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
589 			// left
618 	int leftDepth = _CheckTree(node, node->left, leftNodeCount);