쉽게 배우는 알고리즘-06연습문제

직접 푼 것으로 틀릴 수 있음 주의

I. Red Black Tree:

1. 다음을 해결하여라

① RedBlack tree에 A,L,O,R,I,T,H,M이 차례대로 insertion되는 과정을 나타내시오

 

② ①에서 완성된 RedBlack tree에서 A,L,O,R,I,T,H,M이 차례대로 deletion되는 과정을 나타내시오

2. 다음을 해결하여라

① RedBlack tree에 S,O,F,T,W,A,R,E이 차례대로 insertion되는 과정을 나타내시오

② ①에서 완성된 RedBlack tree에서 S,O,F,T,W,A,R,E 이 차례대로 deletion되는 과정을 나타내시오

II. 2-3 트리

1. 다음과 같은 2-3 트리가 있다.

다음과 같은 동작이 순서대로 이루어질 때 2-3 트리 모양을 각각 그리시오.

 +5 +70 +8 +50 +7 +3 +65 +75

.

2. 다음과 같은 2-3 트리가 있다.

다음과 같은 동작이 순서대로 이루어질 때 2-3 트리 모양을 각각 그리시오.

 -70 -12 -5

III. B트리

1.다음과 같은 B트리가 주어져 있다. (max 노드 수: 5, 최소 노드 수: 2)

다음과 같은 동작이 순서대로 이루어질 때 B 트리 모양을 각각 그리시오.

(단 여유 있는 형제노드 보는 과정 없이 overflow이면 바로 split 한다고 가정함)

① 키 18 삽입

② 키 16 삽입

 

2. 다음과 같은 B트리가 주어져 있다.

(max 노드 수: 4, 최소 노드 수: 2, 대체노드: 직후원소, 병합: 왼쪽 형제))

다음과 같은 동작이 순서대로 이루어질 때 B 트리 모양을 각각 그리시오.

 ① 키 22 삭제

② 키 19 삭제