재시민

삽입연산

void RBtree::RBTinsert(itemType k, infoType info)

{

	x = head; p = head; g = head;



	while (x != z) // 전달받은키값이들어갈노드의위치를탐색한다

	{

		gg = g; g = p; p = x;

		x = (k < x->key) ? x->l : x->r;

		if (x->l->tag && x->r->tag) split(k);

	}



	x = new node(k, info, 1, z, z); // 위치를탐색한x에새로운노드를생성한다



	// 부모노드인p와비교하여l,r 를결정한다.

	if (k < p->key) p->l = x;

	else p->r = x;

	split(k);

	head->r->tag = black;

}

회전

struct node* rotate(itemType k, node* y)// k - 탐색키, y - 회전할 두 노드의 그 위 노드 포인터
	{
		struct node* high, * low;

		high = (k < y->key) ? y->l : y->r;

		if (k < high->key) // 우회전

		{

			low = high->l; // 자식은 부모의 왼쪽 노드

			high->l = low->r; // 부모의 왼쪽 노드는 자식의 오른쪽 노드 

			low->r = high; // 자식의 오른쪽 노드는 부모 => 역전

		}

		else // 좌회전
		{

			low = high->r;

			high->r = low->l;

			low->l = high;

		}
		// 키값에 따른 서브트리 위치 변경
		if (k < y->key) y->l = low;

		else y->r = low;

		return low;
	}

스플릿 (분할)

void RBtree::split(itemType k)

{

	x->tag = red;

	x->l->tag = black;//NILL

	x->r->tag = black;//NILL



	if (p->tag)//부모가 레드라면

	{

		g->tag = red;

		if (k < g->key != k < p->key) p = rotate(k, g); // p = g->l, x = p->r 이거나, p = g->r, x = p->l 일때

		x = rotate(k, gg);

		x->tag = black;

	}

}

탐색은 BST 탐색과 똑같음

특징

• BST 는 편향트리 (skewed tree) 로 불균형 트리가 될 수 있는 반면 RBTree 는 균형 트리이다.
• 따라서, 모든 삽입, 제거, 탐색 연산은 O(logn)