#13. 트리(Tree)

 

트리(Tree)란?

트리는 비선형 자료구조 중 하나로, 나무를 거꾸로 뒤집어 놓은 듯한 모양으로 인해 트리(Tree)라고 불린다. 마치 회사 조직도나 가계도처럼 생긴 트리는 계층적 구조를 잘 표현할 수 있다. 트리는 그래프의 일종으로 노드(Node)와 간선(Edge)으로 이루어져 있다. 트리에서 사용하는 용어는 다음과 같다.

• 루트 노드(root node) : 부모노드가 없는 노드
• 부모 노드(parent node) : 루트 노드 방향으로 연결된 노드
• 자식 노드(child node) : 루트 노드의 반대 방향으로 연결된 노드
• 단말 노드(leaf node) : 자식 노드가 없는 노드
• 형제 노드(sibling node) :  부모 노드가 같은 노드
• 레벨(level) : 루트노드로부터 노드의 상대적 위치를 의미
• 높이(height) : 트리의 최대 레벨 + 1을 의미
• 차수(degree) : 자식 노드의 개수를 의미

트리의 특징

• 편향 트리가 아닌 이상 일반적으로 삽입이나 삭제 수행 시 O(logN)의 시간복잡도를 갖는다.
• 트리에는 사이클이 존재할 수 없다.(사이클이 없어서 계층적 관계를 표현할 수 있다.)
• 트리는 자기 참조적 구조를 가지고 있어 특정 노드에서 서브 트리 전체를 나타내거나 탐색할 수 있다.
• 이진 탐색 트리와 같은 정렬된 트리 구조 → 범위 검색에 유리, 효율적인 검색
• 불균형한 트리의 경우 재조정이 필요할 수 있어 추가적인 연산이 필요하다.
• 트리에서 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드를 가진다.

이진 트리

이진 트리란 자식 노드가 최대 2개인 트리다. 이진 트리의 종류는 다음과 같다.

• 완전 이진 트리(complete binary tree) : 트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며, 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있는 트리.
• 포화 이진 트리(perfect binary tree) : 트리의 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리.
• 이진 탐색 트리(BST, Binary Search tree) : 한 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드들로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리. 

Tree | 👨🏻‍💻 Tech Interview (gyoogle.dev)

[Java][자료구조] Tree (1) - 트리의 정의와 특성, 이진트리에 대하여 (tistory.com)

[Data Structure] Tree(트리) 자료구조 | 트리의 특징 | 트리의 구성요소 | 트리의 종류 | 트리의 활용 | 트리의 장점 (tistory.com)