[DS] AVL Tree

immanuelk1m·2023년 6월 9일

DS

목록 보기

4/6

Balance Factor

LL case

Right lotation

tree rotateRR(tree A)
{	
	tree B = A->left;
    A->left = B->right;
    B->right = A;
    return B;
}

RR case

Left lotation

tree rotateRR(tree A)
{
	tree B = A->right;
    A->right = B->left;
    B->left = A;
    return B
}

LR Case

tree rotateLR(tree A)
{
	tree B = A->left;
    A->left = rotateRR(B);
    return rotateLL(A);
}

RL case

tree rotateRL(tree A)
{
	tree B = A->left;
    A->right = rotateLL(B);
    return rotateRR(A);
}

Rebalance

숫자 1,2와 부호에 따라 case가 달라진다.

tree rebalance(tree node) {	
	
	if(balanceFactor(node) == 2) // L case
	{
		if(balanceFactor(node->left) == 1) // LL case
		{
			node = rotateLL(node);
		}
		else // LR case
		{
			node = rotateLR(node);
		}
			
	}
	else if(balanceFactor(node) == -2) // R case
	{
		if(balanceFactor(node->right) <= -1) // RR case
		{
			node = rotateRR(node);
		}	
		else // RL case
		{
			node = rotateRL(node);
		}
			
	}
	return node;
}