06 검색 트리

record : 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위

field : 레코드에서 각각의 정보를 나타내는 부분

search key / key : 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 (하나 또는 두개이상)

search tree : 각 노드가 규칙에 맞게 하나씩의 키를 가지고 있고 이를 통해 해당 레코드가 저장된 위치를 알 수 있다.

트리의 자료구조 : 배열 또는 포인터를 이용한 구조체

 

Binary Search Tree (BST)

1. 각 노드는 서로 다른 키 값을 하나씩 갖는다.

2. 최상위 레벨에 루트 노드가 있고 각 노드는 최대 두 개의 자식 노드를 갖는다.

3. 임의의 노드의 키 값은 자신의 왼쪽에 있는 모든 노드의 키 값보다 크고, 오른쪽에 있는 모든 노드의 키 값보다 작다.

 

검색알고리즘

treeSearch(t,x)
{
	if (t=NIL or key[t] = x) then return t;
	if (x < key[t])
		then return treeSearch(left[t], x);
		else return treeSearch(right[t], x);
}

 

삽입알고리즘

treeInsert(t, x)
{
	if (t=NIL) then {
		key[r] ← x; left[r] ← NIL; right[r] ← NIL;
		return r;
	}
	if (x < key(t))
		then {left[t] ← treeInsert(left[t], x); return t;}
		else {right[t] ← treeInsert(right[t], x); return t;}
}

검색과 삽입의 수행 시간은 $\Theta(logn)$

 

삭제알고리즘

case1) r이 leaf node인 경우 :

case2) r의 자식 노드가 하나인 경우

case3) r의 자식 노드가 두 개인 경우

sketchDelete(t, r)
{
	if (r이 leaf node) then
		그냥 r을 버린다;
	else if (r의 자식이 하나만 있음) then
		r의 부모가 r의 자식을 직접 가리키도록 한다;
	else {
		r의 오른쪽 서브트리의 최소원소노드 s를 삭제하고,
		s를 r자리에 놓는다;
	}
}

 

Red-Black Tree (RB Tree)

항상 균형이 잡힌 BST를 만들기 위한 자료구조

1. 루트는 블랙이다.

2. 모든 리프(NIL)은 블랙이다.

3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.