자료구조 - 트리(Tree), 이진트리(Binary Tree)

트리의 개념

트리(Tree)란 노드(Node)와 간선(Edge)으로 구성된 계층적 자료구조다. 보통 루트(Root)라 불리는 최상단 노드에서 시작해서 여러 개의 자식 노드를 가지는 구조로 이루어져 있다. 쉽게 말해 하나의 부모 노드 아래에 여러 자식 노드가 붙어 있고, 자식들이 다시 자식을 가질 수 있는 구조인 것이다. 트리는 노드 사이에 순환이 없는 비순환 그래프의 한 종류이기도 하다.  

 

트리에서 자주 쓰이는 용어들

• 노드(Node): 트리를 구성하는 기본 원소
• 루트 노드(Root Node): 트리의 최상단에 있는 노드
• 리프 노드(Leaf Node): 자식 노드가 없는 노드
• 부모 노드(Parent Node): 루트 노드 방향으로 직접 연결된 노드
• 자식 노드(Child Node): 루트 노드 반대 방향으로 직접 연결된 노드
• 형제 노드(Siblings Node): 같은 부모 노드를 갖는 노드들
• 간선(Edge): 노드들 간의 연결
• 레벨(Level): 특정 노드가 루트로부터 떨어져 있는 거리
• 깊이(Depth): 루트에서 특정 노드까지의 거리
• 높이(Height): 루트에서 가장 깊은 리프 노드까지의 거리
• 너비(Width): 가장 많은 노드를 가진 레벨의 크기
• 크기(Size): 노드의 개수
• 차수(Degree): 각 노드의 자식의 개수
• 트리의 차수(Degree of tree): 트리의 최대 차수

 

메모리 관점에서 트리의 특징

트리는 계층적인 구조를 갖기 때문에, 각 노드가 자식 노드로의 포인터를 포함한다. 이 때문에 메모리에서 동적 할당을 사용하는 경우가 많다. 이처럼 트리는 포인터 기반 자료구조라서 각 노드가 데이터를 저장하는 것 외에도 포인터 공간을 차지한다. 포인터는 자식 노드를 가리키기 때문에 트리가 클수록 추가적인 메모리 사용량이 늘어난다. 이를 해결하기 위해, 트리의 균형을 유지하는 것이 중요하다.

트리의 노드가 균형을 이루고 있을 경우, 메모리 효율이 좋다. 균형 트리에서는 트리의 깊이가 log n에 가까우므로, 최소한의 메모리로도 원하는 데이터를 빠르게 찾을 수 있다. 하지만 불균형 트리에서는 한쪽 방향으로 깊이가 길어질 수 있어, 특정 노드를 찾는데 시간이 오래 걸리고 메모리 사용도 비효율적일 수 있다.

균형 트리란?
균형 트리는 노드의 삽입, 삭제 후에도 트리의 높이가 너무 크지 않도록 유지하는 이진 트리의 한 종류이다. 이는 트리의 성능을 최적화하고, 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해 필요하다.
균형트리는 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 일정 범위 내에 있도록 유지한다. 또한, 새로운 노드가 삽입되거나 삭제될 때마다 트리가 균형을 잃지 않도록 조정한다. 이 과정에서 회전(rotate) 연산을 통해 구조를 재조정하게 된다.
균형 트리의 예로 AVL 트리와 레드-블랙 트리가 있다.

 

 

트리의 장점과 단점

장점

• 계층적 데이터 표현, 즉 부모-자식 관계를 표현하는 데 뛰어나다.
• 이진 트리, B-트리, 힙 트리 등 다양한 변형이 존재하는 등, 다양한 응용 분야에서 사용할 수 있는 자료구조이다.

단점

• 구현이 다소 복잡하다. 특히, 균형 트리나 트라이 같은 고급 트리 구조는 코드가 복잡해질 수 있다.
• 각 노드가 자식 노드에 대한 포인터를 유지해야 하기 때문에 추가적인 메모리 공간이 필요하다.

 

트리의 사용 사례

• 계층적인 데이터를 표현해야 하는 경우
  • 파일 시스템에서 디렉토리와 파일을 계층적으로 표현할 때
  • HTML, XML 같은 문서 구조를 표현할 때
  • 조직도나 계보도 같은 계층적 관계를 나타낼 때
• 그래프 탐색 및 경로 찾기
  • DFS나 BFS를 사용해 그래프나 트리 구조를 탐색할 때
  • 네트워크, 지도, 게임 등에서 경로 탐색 알고리즘에 트리를 사용할 때
• 구조적인 데이터의 압축이나 최적화가 필요한 경우
  • 허프만 코딩처럼 데이터 압축 알고리즘에서 트리를 이용해 최적화 할 때
  • 트라이(Trie) 자료구조를 사용해 문자열 집합을 효율적으로 저장하고 검색할 때 (ex. 사전, 자동완성)

 

이진 트리의 개념

이진 트리(Binary Tree)란 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조다. 이 두 자식은 보통 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 나뉘며, 각각 별도의 포인터로 연결된다. 이진 트리는 부모-자식 관계를 계층적으로 나타내기 때문에, 데이터를 효율적으로 관리하거나 탐색할 수 있는 특징을 가진다.

 이진 트리에서 중요한 점은 균형이다. 트리가 균형을 이루면 탐색, 삽입, 삭제 연산이 효율적으로 수행되지만, 불균형한 경우 성능이 저하될 수 있다.

 

 

이진 트리의 종류

1. 완전 이진 트리(Complete Binary Tree)

모든 레벨이 꽉 차 있거나 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리다. 마지막 레벨의 노드는 왼쪽부터 차례로 채워진다.

2. 포화 이진 트리(Full Binary Tree)

모든 노드가 자식 노드를 0개 또는 정확히 두 개씩 가지고 모든 리프 노드가 동일한 깊이에 있는 이진 트리다.

3. 균형 이진 트리(Balanced Binary Tree)

트리의 왼쪽과 오른쪽 서브트리 높이 차이가 1 이하인 이진 트리다. 위 이미지에서 불균형 이진 트리는 왼쪽 서브트리의 높이가 3이고, 오른쪽 서브트리의 높이가 0이기 때문에 불균형이다. 균형 이진 트리의 대표적인 예로 AVL 트리, 레드-블랙 트리가 있다.

4. 이진 탐색트리(Binary Search Tree, BST)

이진 탐색 트리는 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 크다는 규칙을 가진다. 이 규칙 덕분에 탐색, 삽입, 삭제가 효율적으로 이루어질 수 있다. 

 

 

이진 트리의 순회

전위 순회(Preorder)

순서는 부모 -> 왼쪽 자식 -> 오른쪽 자식이다. 먼저 부모 노드를 방문하고, 그 후 왼쪽과 오른쪽 자식을 차례로 방문하는 방식이다.

중위 순회(Inorder)

순서는 왼쪽 자식 -> 부모 -> 오른쪽 자식이다. 이진 탐색 트리에서 중위 순회를 하면 노드의 값이 오름차순으로 정렬된다.

후위 순회(Postorder)

순서는 왼쪽 자식 -> 오른쪽 자식 -> 부모이다. 자식 노드를 먼저 모두 방문한 후에 부모 노드를 방문하는 방식으로, 트리 구조를 삭제하거나 정리할 때 유용하다.

 

 

이진 트리의 장점과 단점

장점

• 이진 트리는 노드가 최대 두 개의 자식을 가질 수 있는 단순한 구조를 가지고 있어 구현이 쉽고 이해하기 쉽다.
• 이진 트리에서는 노드를 추가하거나 삭제하는 과정이 비교적 간단하다.

단점

• 이진 트리는 삽입 순서에 따라 구조가 불균형해질 수 있다.
  • 구조가 불군형한 경우, 탐색이나 삽입, 삭제 연산의 시간 복잡도가 O(n)으로 증가할 수 있다.
• 일반 이진 트리는 이진 탐색 트리와 달리 탐색 효율성이 떨어질 수 있다.