[자료구조] 트리(Tree)

트리란?

트리는 그래프의 일종으로 계층적인 구조를 가지며 노드(Node)로 구성된다.

각 노드는 데이터를 포함하고, 다음 노드들과 연결될 수 있다.

 

용어

루트 노드(Root)

- 부모가 없는 트리의 최상위 노드

- 트리는 하나의 루트 노드 가짐

 

부모 노드(Parent)

- 자식 노드를 가지는 노드로 상대적 개념

- 2의 부모 노드는 1

- 4의 부모 노드는 2

 

자식 노드(Child)

- 부모 노드로 부터 가리켜지는 하위 노드

- 1의 자식 노드는 2, 3

- 2의 자식 노드는 4, 5

 

리프 노드(Leaf)

- 자식 노드가 없는 트리의 말단 노드

- 4, 5, 6이 해당

 

형제 노드(Sibling)

- 같은 부모를 가지는 노드

- 2, 3은 1을 부모 노드로 둔 형제 노드

 

레벨(Level)

- 트리의 각 노드가 어느 깊이에 위치하는지 나타내는 값

- 루트 노드의 레벨은 1

 

높이(Height)

- 트리의 최대 높이를 의미

- 리프 노드에서 루트 노드까지 최대 경로의 간선(edge)의 수

- 4(리프 노드) -> 1(루트 노드) = 2

 

깊이(Depth)

- 특정 노드에서 루트 노드까지 경로의 간선(edge)의 수

- 2의 깊이 = 1

 

 종류

이진 트리(Binary Tree)

각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리

 

- 정 이진 트리

모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리

 

- 완전 이진 트리

모든 레벨이 채워져 있거나, 마지막 레벨에서 노드들이 왼쪽부터 순서대로 채워진 트리

 

- 포화 이진 트리

모든 내부 노드가 2개의 자식 노드를 가지고, 모든 리프 노드가 같은 레벨에 있는 트리

 

- 이진 탐색 트리

왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 트리

 

- 힙(Heap)

완전 이진 트리의 일종

부모 노드가 자식 노드보다 크거나, 작도록 유지

 

 

주요 연산

삽입

새로운 노드를 트리에 추가하는 연산

 

삭제

특정 노드를 트리에서 삭제하는 연산

 

탐색

특정 노드를 트리에서 찾는 연산

 

순회

트리의 노드를 특정한 순서로 방문하는 연산

- 전위 순회

- 중위 순회

- 후위 순회

- 레벨 순회