[Data Structure] Trees - 트리구조

많은 자료구조 중에서 자주 사용되는 구조 중 하나는 트리구조이다. 어떤 웹사이트에서, 사이트맵 이라는 걸 본 적이 있다면 이해하기 쉽다. 또, 우리가 사용하는 PC를 폴더단위로 관리한다면, 더 이해하기가 쉽다.

따오기라는 폴더 안에는 꿩, 가마우지, 새폴더, 새 새폴더 라는 이름의 4개의 폴더가 있다. 하나의 부모 아래에 여러개의 자식이 있는 구조. 이게 트리구조 다. 우리가 자료를 찾거나 정리하기 위해 사용하는 자료구조 중에서 트리를 기반으로 한 다양한 구조가 있다.

 

Binary Tree ( 이진 트리 )

이진 트리는 하나의 부모가 가질 수 있는 자식의 수가 최대 2개인 트리를 말한다.

Full Binary Tree ( 포화 이진 트리 )

포화 이진 트리는 모든 부모노드가 두 개의 자식노드를 가지고 있는 경우를 일컫는다.

포화 이진트리의 노드 개수는 2^(h+1) - 1 개이다. 아래의 그림은 h가 2이기때문에 2^3 - 1 = 7개의 노드를 갖는다.

Complete Binary Tree ( 완전 이진 트리 )

완전 이진 트리는 새로운 노드를 추가할 때 왼쪽부터 추가하거나, 기존의 노드를 제거할 때 오른족부터 제거하는 트리를 말한다.

Binary Search Tree ( 이진 탐색 트리 )

이진 탐색 트리는 이전에 설명한 이진탐색과 위에서 설명한 이진트리가 결합한 구조이다.

새로운 노드를 추가할 때, 부모노드보다 값이 작으면 부모의 왼쪽자식에, 부모노드보다 값이 크면 부모의 오른쪽 자식에 노드를 추가한다.

위 그림과 같은 트리가 있을 때, 새로운 노드를 추가해보자. 이 노드는 값이 1이다.

1은 3보다 작기때문에, 3의 자식노드 중 작은 값인 왼쪽노드로 내려간다.

이번에도 1은 2보다 작기때문에 2의 왼쪽 자식으로 내려가고, 만약 해당 위치가 null이면 그 자리를 차지한다.

이번에는 위의 트리에 값이 4인 노드를 넣어보자.

4는 3보다 크기에 3의 오른쪽 자식으로 내려간다. 4는 다시, 5보다 작기때문에 5의 왼쪽자식으로 내려가 결국 아래의 그림과 같은 형태로 트리맵이 형성된다.

이진트리는 자주 사용되는 자료구조인 만큼, 개념을 잘 이해하는 것이 중요하다.

추가적으로 Red-Black Tree 등 노드를 추가 혹은 삭제했을 때 루트노드를 기준으로 양쪽의 밸런스가 잘 맞도록 유지해주는 트리도 있다. 기회가 있다면 새로운 글로 작성하도록 하겠다.