[자료구조] 2-3-4 Tree, Red-Black Tree

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

 

이번 시간에는 2-3 Tree의 확장 버전인 2-3-4 Tree에 대하여 배웠으며, 이를 Red-Black Tree로 표현하여 보았다.

2-3 Tree가 궁금하다면 이전 글을 먼저 확인해보길 권장한다.

[자료구조] AVL Tree, 2-3 Tree

 

2-3-4 Tree

• 각 Node는 1, 2개 또는 3개의 key값을 갖는다.
• 각 Node는 최대 4개의 child를 갖을 수 있다.
• 각 Node들은 chlid를 1개만 갖을수는 없다. 아예 없거나 or 2, 3, 4개의 child를 갖어야 한다.\
• Root에서 모든 leaf노드 까지의 거리가 같다.
• 노드의 수가 N일때 2-3-4 Tree의 높이는 O(logN)이다. 이를 이전의 2-3 Tree와 동일한 방식으로 이해 가능하다.

 

2-3-4 Tree insert

● Algorithm은 이전의 2-3 tree와 유사하다.

● But 2-3 Tree에서와는 다르게 split을 한다.

2-3 Tree 에서는 leaf 까지 내려 간 후, 다시 역으로 올라오면서 split을 한다.

하지만 2-3-4 Tree 에서는 Search 하면서 내려갈때 가득 찬 Node를 만나면, 미리 split을 하면서 내려간다.

그림으로 확인해보자.

 

한가지 의문이 든다. 2-3 Tree 에서는 왜 이러한 방식이 불가능 했을까?

이는 값이 2개라 2개로 나누면 중간에 낄수있는 값이 없기 때문이다.

 

2-3-4 Tree 의 improvement?

저장장치 RAM에서는 모든 위치에 대한 접근 시간이 동일하지만, HDD에서는 그렇지 않다.

HDD 에서는 한 위치(한 노드)에서 다른 위치의 값(다른 노드)을 읽기 위해서는 헤드가 이동을 해야하기 때문에 노드간의 이동의 비용이 크다.

 

따라서 Tree의 층 수를 최대한 줄여야 하기에, 한Node에 많은 데이터를 담으면서 Tree의 높이를 줄이는 것 이다.

예를 들어 BST에서는 10층을 사용해야 할 tree가 2-3-4 tree에서는 3층이면 해결 가능해진다.

 

또한 2-3-4 트리는 AVL과 비교했을 때 새로운 노드와 링크를 생성하는데 드는 비용은 적다.

 

결론 : 2-3-4 트리에서는 링크를 따라 '왔다 갔다'하는 작업을 최소화할 필요가 있다.

=> root로부터 내려가면서 노드가 가득차 있으면 바로 split을 진행한다.

=> 추후 어떤 작업을 해도 parent는 split해줄 필요없이 한 자리가 남아있게된다.

 

메인메모리(RAM)에서는 큰 차이가 없을 수 있지만 HDD에서는 유용하다. Free Block List on File System 같이 하나하나에 많은 정보를 저장하기 때문에 노드간의 이동이 최소화 될수있다.

이를 좀더 확장하면 B-Tree 라는 알고리즘도 나온다. 이는 생략하겠다.

 

 

Red-Black Tree

Red-Black Tree는 2-3-4 Tree의 다른 표현 방식이다.

 

표현방식이 다를 뿐 핵심 logic은 동일하다. 이점을 생각하면 RB-tree를 공부한다면 한결 가볍게 느껴진다.

 

"다른 표현 방식" 의 의미를 그림을 통하여 확인해 보자.

 

1) 노드에 key값이 1개인 경우

2) 노드에 key값이 2개인 경우

RB-tree에서 빨간색의 edge는 2-3-4 tree에서 한 노드에 있던 값들의 관계를 나타낸다.

다음 그림에서는 2-3-4 tree에서 a와 b 의 관계를, RB-tree에서는 red edge로 표현해주고 있다.

나머지 edge들은 원래와 와 똑같이 black으로 설정 해준다.

3) 노드에 key값이 3개인 경우

위의 사진에서 a-b-c 는 한 Node안에 있는 관계이다. 따라서 이를 RB-tree로 바꾸면 a-b-c가 red edge로 연결된다.

 

Red-Black Tree Observations

1) Root Node에서 부터 RB-tree를 따라 끝까지 내려가면서 leaf 까지 도달하면, 지나치면서 확인한 black link의 수가 모두 동일하다.

-> 이는 2-3-4 tree 에서도 원래 있던 link가 RB-tree의 black link가 된것이니 당연하다.

 

2) 트리를 내려갈때 연속된 Red link는 불가능 하다.

-> 만약 K개의 black-edge가 있다면, Red-edge의 최소는 0개이며 최대 K+1개 까지 가능하다.

-> 결과적으로 총 경로의 길이는 0부터 2K+1 까지 가능해진다.

-> 이말은 즉, Search하는데 O(logN)이 걸린다는 의미이다.

 

 

RB-Tree에 관한 자세한 글은 내가 자세하게 정리해 논 다음 글을 확인하길 권장한다.

[알고리즘] Red-Black Tree : 레드 블랙 트리