트리

목차

트리란?

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

트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 

 

트리 구조에서 사용되는 기본 용어

노드 (Node)

• 트리를 구성하고 있는 기본 요소
• 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
• A, B, C, D, E, F, G, H, I, J

간선 (Edge)

• 노드와 노드 간의 연결선

루트 노드 (Root Node)

• 트리 구조에서 부모가 없는 최상위 노드
• root node : A

부모 노드 (Parent Node)

• 자식 노드를 가진 노드
• H, I에 부모 노드는 D

자식 노드 (Child node)

• 부모 노드의 하위 노드
• 노드 D의 자식 노드는 H, I

형제 노드 (Sibling node)

• 같은 부모를 가지는 노드
• H, I는 같은 부모를 가지는 형제 노드

리프 노드(leaf node)

• 자식 노드가 없는 노드
• H, I, J, F, G

깊이 (depth)

• 루트에서 어떤 노드까지의 간선(Edge) 수
• 루트 노드의 깊이 : 0
• D의 깊이 : 2

높이 (height)

• 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수
• 리프 노드의 높이 : 0
• A 노드의 높이 : 3

트리의 특징

• 하나의 루트 노드와 0개 이상의 하위 트리로 구성
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조
• 트리내에 또 다른 트리가 있는 재귀적 자료구조
• 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다.
• 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다.

트리의 종류

이진트리란?

• 이진 트리(binary tree)는 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리로, 트리 중에서 가장 많이 쓰이며 서브 트리 또한 모두 이진 트리여야 하기 때문에 순환적으로 정의되고 있다.
• 0~2개의 자식 노드가 존재할 수 있고, 모든 노드의 차수는 2 이하이다. 이진 트리에는 서브 트리간의 순서가 존재해 왼쪽 서브 트리와 오른쪽 서브 트리는 구별된다.

 

1. 완전 이진 트리트리

• 모든 높이에서 노드가 꽉 차 있는 이진 트리. 즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
• 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
  
  

2. 포화 이진 트리

• 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.
• 모든 내부 노드가 두 개의 자식 노드를 갖는다.
• 모든 말단 노드가 동일한 깊이 또는 레벨을 가진다.

 

 

 

 

 

3. 이진 탐색 트리

• 각 노드의 값이 왼쪽 서브트리에 속한 모든 노드의 값보다 크고 오른쪽 서브트리에 속한 모든 노드의 값보다 작은 이진 트리이다. 
• 이진 탐색 트리는 데이터를 효율적으로 검색할 수 있다.
• 원하는 값을 찾을 때까지 현재의 노드값보다 찾고자하는 값이 작으면 왼쪽으로 움직이고, 크면 오른쪽으로 움직인다. 이렇게 원하는 값을 더 빠르게 찾을 수 있게 된다.