Ch06 검색트리

01 레코드, 키의 정의 및 검색 트리

- 이진 검색 트리 : 자료를 찾는 색인 역할하는 자료구조 중 하나

● 레코드

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

- 사람의 레코드 : 주민번호, 이름, 집주소, 집 전화번호 ...

- 검색 트리는 개체의 레코드 저장, 검색 (대표할 수 있는 필드만으로 )

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

● 검색키, 키

:  다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드

- 키는 필드 하나 or 필드 복수 개

● 검색트리 

- 한 노드에서 최대 몇 개의 자식 노드로 분기?

1 이진 검색 트리 : 최대 2개,

2 다진 검색 트리 

- 저장되는 장소?

1 내부 검색 트리 : 메인 메모리 내에, 메인 메모리에 모든 키를 수용할 수 있으면

2 외부 검색 트리 : 외부(디스크)에, 메인 메모리에 모든 키를 수용할 수 없으면, 디스크 접근 시간이 검색의 효율 좌우

- 검색키가 포함하는 필드의 수?

1 일차원 검색 트리 : 키를 구성하는 필드가 하나 ex)이진 검색, 다진 검색, B-, AVL-, RB트리 등

2 다차원 검색 트리 : 두 개 이상

- 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다 이를 통해 해당 레코드가 저장된 위치를 알 수 있다

 

 

02 이진 검색 트리

- 이진검색트리의 각 노드는 키 값을 하나씩 갖음 • 각 노드의 키 값은 모두 달라야 함

• 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식만 갖음

• 임의의 노드의 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키 값보다 작음

 

- 이진 검색 트리의 서브트리도 이진검색트리를 유지함

 

02-1. 검색

treeSearch(t, x)
▷ t: 트리의 루트 노드
▷ x: 검색하고자 하는 키
{
if (t=NIL or key[t]=x) then return t;  // 성공하면 t리턴, 실패하면 NIL리턴
if (x < key[t])
  then return treeSearch(left[t], x);
  else return treeSearch(right[t], x);
}

검색에서 재귀적 관점 ∵ subtree도 binary search tree여서

 

02-2. 삽입

treeInsert(t, x)
▷ t: 트리의 루트 노드
▷ x: 삽입하고자 하는 키
▷ 작업 완료 후 루트 노드의 포인터를 리턴한다
{
if (t=NIL) then { // 루트노드 만듦
 key[r] ← x; left[r] ← NIL; right[r] ← NIL; ▷ r : 새 노드
 return r ;
}
if (x < key(t))
 then {left[t] ← treeInsert(left[t], x); return t;}
 else {right[t] ← treeInsert(right[t], x); return t;}
}

 Ex. 30, 20, 25..... 순서로 원소가 삽입됨

 

● 이진 검색 트리에서의 검색시간 (=삽입시간의 복잡도)

검색 트리의 효율 ~ 검색 트리의 깊이

- 균형이 이상적으로 잡혀 있으면 최악의 경우여도 θ(logn)

- 균형이 맞지 않은 최악의 경우 θ(n)

- 평균적인 검색시간은 θ(logn)

 

02-3. 삭제

Sketch-TreeDelete(t, r)
▷ t: 트리의 루트 노드
▷ r: 삭제하고자 하는 키
{
if (r이 리프 노드) then ▷ Case 1
  그냥 r을 버린다;
else if (r의 자식이 하나만 있음) then ▷ Case 2
  r의 부모가 r의 자식을 직접 가리키도록 한다;
else ▷ Case 3
  r의 오른쪽 서브트리의 최소원소 노드 s를 삭제하고,
  s를 r 자리에 놓는다;
}

삭제 작업 복잡도: O(logn) ~ O(n)

treeDelete(t, r, p)
{
if (r = t) then root ← deleteNode(t); ▷ r이 루트 노드인 경우
else if (r = left[p]) ▷ r이 루트가 아닌 경우
 then left[p] ← deleteNode(r); ▷ r이 p의 왼쪽 자식
 else right[p] ← deleteNode(r); ▷ r이 p의 오른쪽 자식
}
deleteNode(r)
{
if (left[r] = right[r] = NIL) then return NIL; ▷ Case 1
else if (left[r] = NIL and right[r] ≠ NIL) then return right[r]; ▷ Case 2-1
else if (left[r] ≠ NIL and right[r] = NIL) then return left[r]; ▷ Case 2-2
else { ▷ Case 3
s ← right[r];
while (left[s] ≠ NIL)
 {parent ← s; s ← left[s];}
key[r] ← key[s];
if (s = right[r]) then right[r] ← right[s];
 else left[parent] ← right[s];
return r;
}
}

삭제부분 ??

 

저장과 검색에 평균 θ(logn)시간이 소요, 균형이 많이 깨진 경우 θ(n)에 근접한 시간이 소요될 수 있음

이를 해결하기 위해 균형이 잘 맞는 트리를 구성!

 

 

03 레드 블랙 트리

최악의 경우에도 검색의 성능을 어느 정도 보장하는 균형잡힌 검색 트리의 예

 

1. 루트, 외부노드 : black

2. 루트~외부노드 경로는 2개의 연속적인 red node x

3. 루트~외부노드 모든 경로에 있는 black node 수 동일

4. 삽입노드 : red

 

불균형 종류

XYb -> rotation

XYr -> color flip

 

재귀적으로 해결

 

1. 삽입

 

2. 삭제

삭제노드가 red 

삭제노드가 black

 

 

3. 작업 성능 분석

 

키가 총 n개인 레드블랙트리의 가능한 최대 깊이는 O(logn)이다.

• 키가 n개라면 내부노드의 수가 n개

• 트리의 깊이는 ㄴlog n」 +1

• 루트에서 임의의 리프에 이르는 경로의 블랙노드는 아무리 잘 만들어져도ㄴ log n」 +1을 넘을 수 없음

• 레드노드는 두개 연속해서 존재할 수 없으므로 블랙노드보다 적음

• 임의의 리프에 이르는 총 길이는 2(ㄴ log n」 +1)을 넘을 수 없음