[자료구조] Tree(트리)? (개념, 특징, 활용, 파이썬 사용)

 

트리(Tree)는 컴퓨터 과학에서 데이터를 다루기 위한 중요한 자료구조 중 하나입니다. 트리는 노드(Node)들이 가지(branch)를 통해 연결된 계층적 구조를 가지며, 여러 응용 분야에서 활용됩니다. 특히, 계층적 데이터를 다루거나 데이터를 효율적으로 검색, 추가, 삭제하는 작업에 유용하게 쓰입니다.

 

 

기본 개념

• 노드(Node): 트리를 구성하는 기본 요소입니다. 데이터를 저장하며 하나 이상의 자식 노드를 가질 수 있습니다.
• 루트 노드(Root Node): 트리의 최상위에 위치하는 노드입니다. 하나의 트리에는 단 하나의 루트 노드만 존재합니다.
• 부모 노드(Parent Node): 특정 노드의 바로 윗 단계에 위치하는 노드입니다.
• 자식 노드(Child Node): 특정 노드의 하위에 위치하는 노드입니다.
• 형제 노드(Sibling Node): 동일한 부모 노드를 가진 서로 다른 자식 노드들입니다.
• 차수(Degree): 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 합니다.
• 조상(Ancestor): 위쪽으로 간선을 따라가면 만나는 모든 노드입니다.
• 자손(Descendant): 아래쪽으로 간선을 따라가면 만나는 모든 노드입니다.
• 내부 노드(Internal Node): 루트와 리프 노드를 제외한 모든 노드입니다.
• 리프 노드(Leaf Node): 자식 노드가 없는 노드를 말합니다.
• 가지(Branch), 간선(Edge) : 노드와 노드를 연결하는 선입니다.
• 깊이(Depth): 루트 노드로부터 특정 노드까지의 경로 길이입니다.
• 높이(Height): 특정 노드로부터 가장 깊은 리프 노드까지의 최대 경로 길이입니다. 트리의 높이는 루트 노드의 높이로 정의됩니다.

특징

• 비선형 구조: 트리는 비선형 구조를 가지며, 계층적 관계를 표현하는데 적합합니다.
• 계층적 관계: 트리는 일반적으로 상위 레벨의 노드와 하위 레벨의 노드 간에 부모-자식 관계를 가집니다.
• 단방향성: 트리 구조에서 노드들은 오직 위에서 아래로, 또는 부모로부터 자식으로의 단방향 연결만을 가집니다.
• 하나의 루트 노드: 모든 트리에는 정확히 하나의 루트 노드가 존재합니다.
• 순환 없음: 트리는 순환 구조를 가지지 않으며, 어떤 노드로부터 출발하여 같은 노드로 돌아오는 경로가 없습니다.
• 경로: 트리에서 한 노드에서 다른 노드로 가는 길을 경로라 하며, 모든 노드는 루트 노드와의 경로를 정확히 하나만 가집니다.

 

 

활용 예시

• 파일 시스템: 파일 시스템은 트리 구조를 사용하여 파일과 디렉터리의 계층적 관계를 관리합니다. 이때, 각 디렉터리는 트리의 노드로 표현되며, 최상위 디렉토리는 루트 노드가 됩니다.
• 검색 엔진: 검색 엔진은 웹사이트의 데이터를 색인할 때 트리 기반 자료 구조인 이진 검색 트리(Binary Search Tree)나 트라이(Trie) 등을 사용하여 효율적으로 데이터를 저장하고 검색합니다.
• 데이터베이스: 많은 데이터베이스 시스템들은 트리 구조, 특히 B- 트리나 B+-트리 같은 변형된 트리 구조를 사용하여 데이터를 효율적으로 저장하고 검색합니다. 이를 통해 대량의 데이터에 대한 삽입, 삭제, 검색 작업을 빠르게 처리할 수 있습니다.
• 그래픽스: 컴퓨터 그래픽스에서는 장면의 구성 요소들을 계층적으로 관리하기 위해 장면 그래프(Scene Graph)라고 하는 트리 구조를 사용합니다. 이를 통해 객체들의 변환, 애니메이션, 렌더링 등을 효율적으로 처리할 수 있습니다.
• 네트워킹: 네트워크 프로토콜, 예를 들어 IP 라우팅에서는 라우팅 정보를 효율적으로 관리하기 위해 트리 구조를 사용합니다. 특히, 패킷의 목적지 주소를 기반으로 경로를 결정하는 데 있어 트리가 유용하게 쓰입니다.
• 인공지능: 결정 트리(Decision Tree)는 분류(Classification)와 회귀(Regression) 문제에 널리 사용되는 인공지능 모델입니다. 데이터로부터 복잡한 결정 경계를 학습하여 예측을 수행할 수 있는 강력한 도구입니다.
• 게임 개발: 게임 개발에서는 인공지능 캐릭터의 결정-making과 같은 기능을 구현하기 위해 행동 트리(Behavior Tree)를 사용합니다. 행동 트리를 통해 다양한 게임 상황에 따라 어떻게 행동해야 하는지를 효율적으로 정의할 수 있습니다.

 

파이썬에서의 Tree 사용

class Node:
	def __init__(self, value = 0, left = None, right = None):
    	self.value = value
        self.left = left
        self.right = right
        
class BinaryTree:
	def __init__(self):
    	self.root = None
        
bt = BinaryTree() #트리 생성
bt.root = Node(value = 1)
bt.root.left = Node(value = 2)
bt.root.right = Node(value = 3)
bt.root.left.left = Node(value = 4)
bt.root.left.right = Node(value = 5)
bt.root.right.right = Node(value = 6)

 

 

전위, 중위, 후위 순회

• 전위 순회 
  • 현재 노드를 방문합니다.
  • 왼쪽 서브트리를 전위 순회합니다.
  • 오른쪽 서브트리를 전위 순회합니다.
  • 이 방법에서는 노드를 자식 노드들보다 먼저 방문합니다.
  • 따라서, '루트 - 왼쪽 - 오른쪽'의 순서로 노드들을 방문합니다.
• 중위 순회
  • 왼쪽 서브트리를 중위 순회합니다.
  • 현재 노드를 방문합니다.
  • 오른쪽 서브트리를 중위 순회합니다.
  • 이 방법에서는 '왼쪽 - 루트 - 오른쪽'의 순서로 노드를 방문하게 되며, 이진 검색 트리에서 이 순회 방법을 사용하면 오름차순으로 노드들을 방문할 수 있습니다.
• 후위 순회
  • 왼쪽 서브트리를 후위 순회합니다.
  • 오른쪽 서브트리를 후위 순회합니다.
  • 현재 노드를 방문합니다.
  • 이 순서에서는 '왼쪽 - 오른쪽 - 루트' 순서로 노드들을 방문하게 되며, 노드를 자식 노드들이 모두 방문된 후에 방문합니다. 이는 특히, 노드들을 제거하거나 트리를 안전하게 소멸시킬 때 유용합니다.

 

오늘은 트리에 대해서 알아보았습니다.

추가로 Stack과 Queue도 중요한 자료구조이니 함께 확인해주세요!

2024.04.30 - [IT] - [자료구조] Stack과 Queue? (특징, 사용 사례, 예시)

[자료구조] Stack과 Queue? (특징, 사용 사례, 예시)