2-3Tree (2-3트리)

다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알아보겠습니다.

 

2-3트리는 이진트리의 확장 버전입니다.

 

이진트리에서는, 한 노드가 하나의 키값을 가지고 최대 두개의 자식을 가질 수 있었습니다.

 

하지만 2-3트리에서는 한 노드가 두개의 키값을 가질 수 있고, 세개의 자식을 가질 수 있습니다.

 

이진트리에서는 

leftChild , rightChild 이렇게 두개의 자식이 있었다면

 

2-3트리에서는 

leftChild , midChild , rightChild 이렇게 세개의 자식을 가질 수 있다고 생각하면 됩니다.

 

2-3트리는 이진 트리와 비교했을 때 무슨 장점이 있을까요?

 

 

먼저,

데이터 삽입의 예시를 살펴보겠습니다.

 

1. 데이터를 삽입할 때 키 값이 2개 있는 노드가 일시적으로 3개가 되는것처럼 보이지만

   분리할 수 있습니다.

 

 

2. 이진트리였다면 새로운 데이터를 삽입할 때 높이를 높여야 하지만

    아래 그림과 같이 2-3트리의 경우 트리의 높이를 높이지 않고 해결할 수 있습니다.

 

 

 

 

위의 두 예시들을 보면 알 수 있듯,

 

2-3트리는 트리의 전체를 수정하는 것이 아닌

 

국소적인 부분의 수정만으로도 균형을 유지할 수 있다는 것이 장점입니다.

 

하지만 키값이 2개, 자식이 3개이므로 복잡한 면이 있는데요,

 

2-3트리의 성질을 이용하면서도 키값을 하나만 가지는 이진트리처럼 구현한 것이 바로 RedBlackTree(레드블랙트리) 입니다.

 

이번에 알아본 내용을 바탕으로 다음에 레드블랙트리에 대해 알아보겠습니다.