AVL 트리 정리

 

rotate_right 함수

AVLNode *rotate_right(AVLNode *parent)
{
	AVLNode* child = parent->left;
	parent->left = child->right;
	child->right = parent;

	// 새로운 루트를 반환
	return child;
}

parent의 left를 child라 명한다. 
child의 right를 parent의 left로 이동시킨다.
child의 right로 parent를 이동시킨다.
회전된 child 노드를 반환한다.

마지막 부분을 보면 child->right = parent;
기존의 child가 parent 자리로 가고 parent가 child의 오른쪽으로 가야하기에 이해가 쉬움
하지만 왜 parent->left = child->right; 인가?
child의 오른쪽에 parent가 들어간다면 기존에 있던 child의 오른쪽 부분은 parent에 연결해야하기 때문
이진탐색트리의 특성때문에 해당 부분은 parent의 왼쪽에 연결해야함. 

적용예시 및 해설

LL에서 X노드가 parent, Y노드가 child 이다. 

RL에서 하단부를 회전시킨다.
parent 는 Y노드, child는 J 노드가 된다.
J노드의 right를 Y노드의 left에 연결한다.
J노드의 right에 Y노드를 연결한다. 

 

rotate_left 함수

AVLNode *rotate_left(AVLNode *parent)
{
	AVLNode *child = parent->right;
	parent->right = child->left;
	child->left = parent;

	// 새로운 루트 반환
	return child;
}

parent의 right를 child라 명한다. 
child의 left를 parent의 right로 이동시킨다.
child의 left로 parent를 이동시킨다.
회전된 child 노드를 반환한다.

적용예시 및 해설

RR에서 X노드가 parent, Y노드가 child 이다. 

LR에서 하단부를 회전시킨다.
parent 는 Y노드, child는 J 노드가 된다.
J노드의 left를 Y노드의 right에 연결한다.
J노드의 left에 Y노드를 연결한다.