[탐색 트리] 2-3-4 트리

2-3-4 트리란?

탐색트리 중 하나로, 이진 트리가 아니다. 즉, 자식 노드가 2개보다 많을 수 있다.

특징으로

1. 이름처럼 자식 노드의 개수는 2개 또는 3개 또는 4개를 가질 수 있다. (즉, 최소 2개 ~ 최대 4개)

2. 모든 leaf 노드가 같은 level에 존재한다.

3. 삽입 시, leaf 노드에 삽입한다.

 

---

삽입

추가할 key가 root부터 leaf 노드까지 내려가면서, 4-노드이면 split하면서 내려간다.

split할 때 중간 값은 부모 노드로 무조건 올라갈 수 있는데, 그 이유는 key가 내려오면서 4-노드인 경우 split을 이미 해놨기 때문이다.

 

2-3-4 트리의 삽입

 

split하는데 O(1)이 걸리고,

최악의 경우 leaf노드까지 내려가면서 매번 split 해야하므로(log n번), 삽입 시의 시간복잡도는 O(logn)이다.

 

---

삭제

2-3-4 트리에서는 삭제에서 특별한 작업이 진행된다.

삭제하려는 key값이 root부터 leaf 노드까지 내려가면서, 2-노드인 경우 =>  3-노드 또는 4-노드가 되도록 만들어준다.

(underflow가 발생할 수 있기 때문에)

 

아래 <그림 1>에서 root에서 leaf로 내려가면서 [30] 이 2-노드인 것을 발견했다.

그렇다면 형제 노드 중 꿔줄 수 있는 3-노드인 [10,15]에서 빌려오게 된다.

이 때 형제노드의 key는 부모 노드로 올라가고, 부모노드의 key 값이 [30] 노드로 내려오게 된다. (아래 그림에서 20이 내려옴)

(이렇게 형제 노드의 값이 오지 못하는 이유는 [30] 노드에서는 20보다 큰 값이 와야하는 트리의 상황때문이다. 탐색할 때 범위로 찾는 것을 생각하면 이해하기 쉽다!)

 

<그림 1>

 

 

아래 <그림 2>에서는 형제 노드도 형편이 되지 않을 경우, 부모 노드의 key값과 2-노드인 key값, 형제노드의 key값이 병합되는 모습을 보여준다.

<그림2>

추가로 염두할 점은, root 노드인 경우 2-노드여도 위의 작업들을 수행하지 않고 넘어간다. 

아래 그림에서는 root 노드는 넘어갔고, [30]이 2-노드인 상황이고 + 형제 노드가 꿔줄 형 편이 안되므로 -> 병합이 일어난 상황이다.

<그림 3>

 

1) 삭제하고자 하는 key값이 leaf 노드가 아닌 경우

해당 key 값의 predecessor(key보다 작은 값중에 가장 큰 값) 또는 successor(key보다 큰 값중에 가장 작은값)과 자리를 바꾼 후에 삭제한다.

(참고로, predecessor와 successor는 항상 leaf 노드에 위치해있다)

 

2) leaf 노드를 삭제한다.

 

2-노드를 3-노드 또는 4-노드로 바꿔주는 작업을 하는데 O(1)이 걸리고,

최악의 경우 leaf노드까지 내려가면서 매번 해야하므로(log n번), 삽입 시의 시간복잡도는 O(logn)이다.

 

정리하면, 삽입과 삭제 모두 log(n)의 시간복잡도를 가진다.

 

 

---

정리 내용 및 컨텐츠 출처

https://www.youtube.com/watch?v=ad3tnpLCxYk&t=1585s