kernel/util/AVLTreeBase.cpp

84 		while (node->right)
85 			node = node->right;
96 		// The previous node cannot be in the right subtree.
98 			// We have a left subtree, so go to the right-most node.
100 			while (node->right)
101 				node = node->right;
104 			// took the right branch.
122 		if (node->right) {
123 			// We have a right subtree, so go to the left-most node.
124 			node = node->right;
128 			// No right subtree: Backtrack our path and stop, where we
134 			} while (node && previous == node->right);
155 			node = node->right;
177 			node = node->right;
229 				node = node->right;
277 	node->left = left->right;
278 	if (left->right)
279 		left->right->parent = node;
280 	left->right = node;
303 	AVLTreeNode* right = node->right;
305 	*nodeP = right;
307 	right->parent = node->parent;
308 	node->right = right->left;
309 	if (right->left)
310 		right->left->parent = node;
311 	right->left = node;
312 	node->parent = right;
316 	if (right->balance_factor <= 0)
319 		node->balance_factor -= right->balance_factor + 1;
321 	// former right
323 		right->balance_factor--;
325 		right->balance_factor += node->balance_factor - 1;
339 			// left right heavy
357 		// tree is right heavy
358 		AVLTreeNode** right = &(*node)->right;
359 		if ((*right)->balance_factor == RIGHT) {
360 			// right right heavy
363 			// right left heavy
364 			_RotateRight(right);
402 				node = &(*node)->right;
411 	nodeToInsert->right = NULL;
430 			// right
446 		// tree is right heavy
447 		AVLTreeNode** right = &(*node)->right;
448 		if ((*right)->balance_factor == RIGHT) {
449 			// right right heavy
451 		} else if ((*right)->balance_factor == BALANCED) {
452 			// right none heavy
456 			// right left heavy
457 			_RotateRight(right);
483 			// left right heavy
502 	while ((*node)->right) {
505 		node = &(*node)->right;
542 		= (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
546 	if (node->left && node->right) {
551 		replace->right = node->right;
554 		node->right->parent = replace;
568 	} else if (node->right) {
569 		// node has only right child
570 		replace = node->right;
587 		nodeP = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
593 			// right
621 	int rightDepth = _CheckTree(node, node->right, rightNodeCount);