이중 회전을 실행하는 함수를 쓰면, 그 효율은 두 개의 단일 회전을 실행하는 것을 초과해야 한다

967 단어
데이터 구조와 알고리즘 분석 - c 언어 설명 연습4.22 답안
두 개의 단회전을 인공적으로 펼치는 함수다.그림만 그리면 돼.
static Position doubleRotateWithLeft(Position k3) {
	Position k1 = k3->left;
	Position k2 = k1->right;
	k1->right = k2->left;
	k3->left = k2->right;
	k2->left = k1;
	k2->right = k3;
	k1->height = Max(height(k1->left), height(k1->right)) + 1;
	k3->height = Max(height(k3->left), height(k3->right)) + 1;
	k2->height = Max(height(k2->left), height(k2->right)) + 1;
	return k2;
}



static Position doubleRotateWithRight(Position k1) {
	Position k3 = k1->right;
	Position k2 = k3->left;
	k1->right = k2->left;
	k3->left = k2->right;
	k2->left = k1;
	k2->right = k3;
	k1->height = Max(height(k1->left), height(k1->right)) + 1;
	k3->height = Max(height(k3->left), height(k3->right)) + 1;
	k2->height = Max(height(k2->left), height(k2->right)) + 1;
	return k2;
}

좋은 웹페이지 즐겨찾기