Part 1. 데이터 구조 - 트리 데이터 구조

3. 트리 데이터 구조

  생물학적인 의미로 트리(tree)란 말 그대로 뿌리, 줄기, 가지가 있는 거대한 나무를 뜻하며, 컴퓨팅 분야에서의 트리는 이러한 나무를 거꾸로 뒤집은 형태와 비슷하다. 

 

트리

  트리 데이터 구조는 데이터를 선형으로 정렬하는 선형 데이터 구조와 달리 데이터를 계층으로 정렬한다. 트리 데이터 구조의 가장 위쪽에는 나무의 뿌리에 해당하는 루트 노드(Root Node)가 있고, 트리의 나머지 요소들은 이 루트 노드를 기준으로 하위계층으로 구성된다. 루트 노드를 기준으로 아랫 방향으로 또 다른 노드가 연결되는 것을 하위 노드 또는 자식 노드(Child Node)라고 부르며, 해당 노드를 기준으로 로 윗 방향으로 노드가 연결된 것을 상위 노드 또는 부모 노드(Parent Node)라 부른다. 트리구조의 부모 노드는 여러 개의 자식 노드를 가지지만, 자식 노드는 여러 개의 부모 노드를 가지지 않는다. 자식 노드에 여러 개의 부모 노드가 있는 구조는 그래프(Graph)라고도 한다.

 

루트노드, 부모노드와 자식노드

 

  트리 데이터 구조에서, 더 이상 자식노드를 가지지 않는 노드는 말단 노드 또는 리프 노드(Leaf Node)라 부른다. 트리에서 각 노드를 연결하는 선은 에지(edge)라고 부르며, 노드 하나와 그 자식 노드로 이루어진 트리는 하위 트리 또는 서브 트리(Sub Tree)라 부른다. 

 

서브트리 구조

 

  각 노드에는 데이터가 저장되어 있고, 이 때 데이터에는 실제 값과 그를 구분하는 키가 저장될 수 있다. 여기서 키와 값 사이의 관계를 키-값(Key-Value) 유형의 구조라고 하며, 이러한 트리를 탐색하는 과정은 순회(Traversal)이라고 부른다.

 

이진트리

  이진트리(Binary Tree)는 트리 구조중 가장 많이 사용되는 데이터 구조이며, 각 부모노드가 항상 2개의 자식 노드와 연결되어 있어 붙여진 이름이다. 앞서 살펴보았던 트리의 구조가 이진트리의 가장 대표적인 구조이다. 이진트리의 가장 일반적인 유형은 이진 탐색 트리(Binary Search Tree)이며, 노드의 키를 기준으로 정렬한 상태이다. 이진 탐색 트리는 모든 노드의 키가 왼쪽 서브 트리보다 크고 오른쪽 서브 트리보다 작게 정렬되기 때문에, 가장 작은 키를 가진 노드가 루트 노드를 기준으로 가장 왼쪽 말단에 위치하고 가장 큰 키를 가진 노드가 루트 노드를 기준으로 하여 가장 오른쪽 말단에 위치하게 된다.

 

이진 트리 구조

 

  이진 탐색 트리로 할 수 있는 동작은 트리에 노드를 추가하거나, 삭제하고, 특정 노드를 선택해 탐색하고자 하는 키가 존재하는지 확인하는 것이다. 이진 탐색 트리는 트리 구조로 정렬된 데이터를 저장하는 데 효율적이기 때문에 많은 상황에 폭 넓게 사용된다.

 

AVL트리

  AVL(Adelson-Velsky and Landis) 이진트리는 아래와 같이 이진트리의 균형이 깨져 많은 노드가 단 하나의 자식노드만을 가지게 될 때, 트리의 균형을 다시 조정하는 과정을 가지는 트리이다. 즉, AVL 이진트리는 트리의 역할은 유지하되 가능한 한 최소 높이(자식 노드의 계층이 최소)로 다시 구조를 맞추어 균형을 맞추는 것을 말한다. 메모리를 효율적으로 사용하기 위해 트리의 불균형을 해결하는 것은 중요하며, 이렇게 불균형을 해소하기 위해 서브 트리 2개 사이에서 높이차이를 감지하여 균형 조정 과정을 수행하는 것을 트리 회전(Tree Rotation)이라고 한다.

 

이진트리의 불균형 해소(트리회전)

 

  트리의 균형과 트리의 균형을 조정하는 과정은 자세히 다루지 않지만, 이 과정에서 가장 중요한 것은 균형을 맞추는 데 소요되는 시간이다. 자체적으로 균형을 조정하는 트리는 이와 관련된 시간 복잡도가 존재하며, AVL 트리의 경우에는 O(logn)의 시간복잡도를 가진다. AVL 트리는 일부 데이터 베이스 검색 시스템에서 사용된다.

 

RB트리

  RB(Red-Black) 이진 탐색 트리는 자체적으로 균형을 조정한다는 점에서 AVL 이진 탐색 트리와 비슷하지만, AVL 트리보다 효율적

이다. RB트리는 노드마다 빨강 또는 검정으로 해석되는 비트를 포함하며, 일반적으로 루트 노드가 검정이며, 빨강 노드는 검정 노드를 자식으로 갖게 된다. RB 트리는 트리의 구조 덕에 균형을 조정하는 과정에서 트리 회전수가 AVL 트리보다 적고 O(logn) 의 시간 복잡도를 가진다.

 

RB트리

 

B트리

  B트리는 데이터베이스 시스템을 설계할 때 사용되는 데이터 구조로, AVL/RB트리와 같이 자체적인 균형 조정 기능을 갖춘 트리이다. 하지만 B트리는 앞서 소개한 이진 탐색 트리와 달리 자식 노드 3개 이상을 갖는 부모 노드가 존재할 수 있다. 이와 같은 특성 때문에 대부분의 파일 시스템이 데이터 계층구조로 B트리를 사용한다.

 

 

힙

  힙은 트리 기반 데이터 구조로, 실제 프로그래밍에서 가장 많이 사용되는 구조 중 하나이다. 힙은 이진 트리 데이터 구조 중 한 종류로 구분되며, 값이 최대 혹은 최소인 노드에 빠르게 접근하여야 하는 응용 프로그램에 적합한 구조이다. 힙의 구조를 설계하는 방법은 2가지이며, 각각은 최대 힙(Max Heap)과 최소 힙(Min Heap)이라 부른다. 

  최대 힙은 루트 노드가 힙에서 가장 큰 값을 가지고, 노드 각각의 값이 부모 노드의 값보다 작거나 같도록 구성된 것을 말하며, 최소 힙은 루트 노드가 힙에서 가장 작은 값이고 노드 각각의 값이 부모 노드의 값보다 크거나 같도록 구성된 것을 말한다.

 

 

최대 힙과 최소 힙

 

  최소 힙이나 최대 힙을 적용한 응용 프로그램에서 이들의 성능을 대체할 수 있는 다른 데이터 구조는 없다. 추가로, 힙 데이터 구조는 힙 메모리(Heap Memory)와 전혀 다른 개념인 것을 알아야 한다. 힙 메모리는 프로그래머가 작성한 코드에 따라 메모리 공간을 동적으로 할당하고 해제하는 부분이며, 이는 힙 데이터 구조와 아주 다른 방식으로 구현된다.