컬렉션 프레임워크(5) - 검색 강화 컬렉션 1 : 이진트리 구조

 

 

 

검색 기능을 강화한 컬렉션 프레임워크는 대표적으로 TreeSet과 TreeMap이 존재합니다. 당연히 각각 Set 컬렉션, Map 컬렉션이겠죠? 그런데 이 두 개의 컬렉션 프레임워크를 알아보기 전에 이진트리 구조(binary tree)를 이해해야 합니다. 왜냐하면 이 컬렉션들의 구조 자체가 이 이진트리를 이용해 계층적 구조(tree architecture)를 형성하기 때문입니다. 

 

 

---

 

 

○ 이진 트리 구조

 

그럼 기본적으로 이 '이진트리 구조'가 무엇을 의미하는지부터 살펴보겠습니다. 이 이진트리 구조에 대한 이해가 있어야지 우리가 앞으로 살펴볼 TreeSet과 TreeMap과 같은 컬렉션이 왜 "검색 기능이 강화된 컬렉션"인지를 이해할 수 있기 때문이죠. 

 

이진트리 구조는 여러 개의 노드(node)가 트리 모양으로 연결된 구조를 의미합니다. 기본적으로 가장 최상위에 있는 노드를 루트 노드(root node)로 칭합니다. 

 

기본적으로 하나의 노드에는 최대 2개의 노드를 연결할 수 있습니다. 그리고 연결된 이 두 개의 노드는 자식 노드, 상위의 노드를 부모 노드로 칭하죠. 아래 그림과 같은 형태로 이해할 수 있습니다. 

 

 

 

위 이미지에서의 A 노드는 B와 C의 부모 노드이고, B와 C는 A의 자식노드가 되는 것이죠.

 

 

 

 

---

 

 

○ 이진 트리 값 저장 순서

 

두 개의 자식 노드에 값이 있을 때 배치하는 원칙도 있습니다. 부모의 값보다 작은 노드는 왼쪽 - 부모의 값보다 큰 노드는 오른쪽에 배치하는 것입니다. 단순해 보이지만, 특유의 저장 방식과 원칙이 있으므로 이해했다고 착각하지 말고 잘 따라오시기 바랍니다. 

 

우선 [6, 3, 9, 2, 5]라는 다섯개의 값을 순서대로 이진 트리에 저장한다고 가정해 보겠습니다. 

 

1. 우선, 가장 첫 번째 값(6)이 루트 노드(root node)가 됩니다.
2. 다음 숫자(3)를 부모 노드(6)와 비교합니다. 작으므로 왼쪽 자식 노드가 됩니다. 
3. 그 다음 숫자(9)는 부모 노드보다 크므로 오른쪽 자식 노드가 됩니다. 
4. 이번에는 2와 5를 부모 노드(3)와 비교해 왼쪽, 오른쪽으로 배치합니다. 

 

 

위 순서를 통해서 노드를 구성해보면 아래와 같습니다. 

 

 

 

이러한 형태로 노드를 구성하면, 왼쪽 마지막 노드는 가장 작은 값이 되고 오른쪽 마지막 노드는 가장 큰 값이 배치됩니다.

그렇기 때문에 왼쪽 마지막 노드부터 오른쪽 마지막 노드까지 [왼쪽 노드 → 부모 노드 → 오른쪽 노드] 순서로 값을 읽어나가면 이는 오름차순 정렬된 값이 됩니다(2, 3, 5... 6, 9). 반대로 오른쪽 마지막 노드부터 [오른쪽 노드 → 부모 노드 → 왼쪽 노드]로 읽어 나가면 이는 내림 차순 정렬이 되지요(9, 6...5, 3, 2)

 

이진트리가 '검색'에 특화되는 이유는 이러한 형태의 구조에서는 일정한 정렬 규칙이 있기 때문에 그룹핑이 용이하기 때문이죠. 예를 들어 2, 3, 5 노드에 동그라미를 그려 묶어주면 이는 '6 미만의 값'이 되고 위의 6, 9 노드를 묶어주면 이는 '6 이상의 값'이 되기 때문입니다.