- Tree란?
트리(Tree) : 데이터들의 저장, 탐색에 유용한 자료구조
트리를 구성하는 용어들을 정리해보자.
트리는 나무를 거꾸로 뒤집어 놓은 모양이며 따라서 나무 밑둥(root)이 맨 위에 있는 형태이다.
트리에 대하여 이해하기 위해서는 이를 구성하는 용어들에 대한 이해가 필요하다.
노드는 트리를 구성하는 요소이며, 노드와 노드 사이를 이어주는 선을 간선 또는 Edge라고 한다.
노드 중 가장 위에 있는 노드를 루프노드라고 하며, 반대로 가장 밑에 있는 노드를 리프노드라고 한다.
따라서 리프노드는 자식이 없는 노드이다.
간선으로 직접 연결된 노드 중 위에 있는 노드를 부모 노드, 아래에 있는 노드를 자식 노드라고 한다.
같은 부모 노드를 갖고 있는 노드를 형제 노드라고 한다.
위 그림 중 13이 51의 부모 노드이며, 4는 51의 형제 노드이다.
루프 노드를 기준으로 특정 노드까지 거쳐가는 간선의 수를 레벨로 표현할 수 있다.
위 그림에서 19, 2, 13은 레벨 1이고, 3, 51, 4는 레벨 2이다.
이진 트리에 대해 알아보자.
이진 트리란 노드 하나가 최대 2개의 자식 노드를 갖는 트리의 한 종류이다.
- 이진트리를 다양한 방법으로 표현해보자.
먼저, 첫번째 방법으로는 이진트리를 배열로 표현할 수 있는데, 다음과 같은 3가지 규칙을 따른다.
1. 루트 노드를 배열 인덱스 1번에 저장한다
2. 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 X 2 이다.
3. 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 X 2 + 1 이다.
해당 규칙을 이용하여 다음과 같이 표현할 수 있다.
이진트리를 배열로 구현하면 메모리가 낭비된다는 단점이 있다.
곱셈 연산을 사용하여 인덱스로 정하는 규칙이기에, 실제 노드 개수보다 더 많은 공간을 사용하기 때문이다.
(이진트리의 노드 갯수가 N개일 경우, 배열로 생성하는 시간 복잡도는 O(N)이다.)
하지만 구현 난이도가 쉬우므로, 트리의 크기가 작거나 메모리 공간이 넉넉하다면 구현 시간을 단축할 수 있다는 장점이 있다.
두번째 방법은 이진트리를 포인터로 구현하는 방법이다.
이진트리를 포인터로 구현할 때에는 노드가 자식 노드 2개를 가리키는 형태로 구현할 수 있다.
포인터로 표현하는 방식은 배열에 비하여 메모리 낭비가 적지만 반대로 구현 난이도가 어려워진다는 단점이 있다.
마지막 방법은 이진트리를 인접리스트로 구현하는 방법이다.
자식을 리스트로 갖는 인접리스트의 형태로 표현할 수 있다.
해당 방식은 2개 이상의 자식도 표현할 수 있기에 이진트리 외의 다양한 트리 형태에도 적용할 수 있다.
- 이진트리를 데이터를 삽입(구축) 및 탐색하는 방법에 대해 알아보자.
이진트리에 데이터를 삽입하거나, 특정 데이터를 탐색할 경우 다음과 같은 규칙을 따른다.
- 루트 노드를 기준으로 데이터를 비교한다
- 데이터의 크기가 현재 노드보다 작다면 해당 노드의 왼쪽 자식 노드에 삽입한다.
- 데이터의 크기가 현재 노드보다 크다면 해당 노드의 오른쪽 자식 노드에 삽입한다.
3, 4, 2, 8, 9, 7, 1의 순서대로 데이터가 들어오는 경우를 예시로 든다면 다음과 같이 동작한다.
즉 이진 트리에 데이터를 삽입할 경우,
미리 삽입한 후 정렬을 하는 것이 아니라 삽입과 동시에 정렬을 진행한다.