[자료구조] 트리(Tree)

트리

트리(Tree: 나무)는 노드들이 나뭇가지처럼 계층적으로 연결된 비선형 자료구조이다.

• 최상위 노드(root)가 있고 아래에 다른 하위 노드가 있다. 하위 노드 안에는 또 다른 하위 노드가 있는 부모와 자식 형태이다.

트리 특징

• 계층 구조: 트리는 부모-자식 관계를 가지며, 상위 노드를 루트(Root) 노드로 하여 하위 노드들이 계층적으로 연결된다.
• 노드 연결: 각 노드는 하나의 부모 노드와 여러 개의 자식 노드와 연결될 수 있다.
• 방향성: 트리는 간선이 방향성을 가지는 비순환 그래프이다. 즉, 어떤 노드에서 시작해도 유일한 경로로 다른 노드로 이동할 수 있다.
• 계층 구조 표현: 계층적 데이터를 표현하기에 용이하다.

트리 관련 용어

• 노드(node) : 트리의 구성 요소 (ex : A, B, C, D, E, F, G, H, I, J)
• 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 (ex : A)
• 단말 노드(terminal/leaf node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드 (ex : F, G, H, I, J)
• 비단말 노드(nonterminal/internal node) : 단말 노드를 제외한 모든 노드 (ex : A, B, C, D, E)
• 간선(edge) : 노드와 노드를 연결하는 연결선
• 형제(sibling) : 같은 부모를 가지는 노드 (ex : B-C 형제, D-E 형제, F-G 형제, H-I 형제)
• 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 (ex : H의 depth는 3)
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 (ex : Level1 = B, C)
• 차수(degree) : 자식 노드의 개수 (ex : C의 degree = 2, F의 degree = 0)

트리의 종류

이진 트리(Binary Tree)

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

힙(Heap)

트리는 언제 사용될까?

컴퓨터의 디렉터리 구조

우리가 사용하는 운영체제(Windows, Linux 등)의 디렉터리 구조는 트리로 이루어져 있다.

조직도, 대진표