[자료구조] [알고리즘] Tree

휘·2024년 5월 2일

Tree

무방향, 사이크클이 없는 연결 그래프, 계층적 자료구조

루트노드 --> 왼쪽 서브트리 --> 오른쪽 서브트리 의 순서로 순회하는 방식이다. 깊이 우선 순회라고도 불린다.

왼쪽 서브트리 --> 노드 --> 오른쪽 서브트리 의 순서로 순회하는 방식이다. 대칭 순회라고도 불린다.

왼쪽 서브트리 --> 오른쪽 서브트리 --> 노드 의 순서로 순회하는 방식이다.

트리 자료구조는 여러 가지 유형이 있는데, 그중 가장 기본이 되는 트리는 이진 트리(Binary Tree) 구조이다.

트리의 특정 노드는 자식의 개수를 제한 없이 가질 수 있는데, 이때, 최대 2개의 자식 노드만 가질 수 있다 는 조건을 추가한것을 이진트리라고 부른다.
쉽게 말해, 노드가 왼쪽 자식 과 오른쪽 자식을 갖는 특징을 가진다.

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

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리.
마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
※ 힙(Heap)은 완전 이진 트리의 일종이다.

포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다.

높이가 h이고 하나의 노드를 가진 트리의 높이가 1이라면 최대 노드 수는 2^h - 1이고 높이가 0이라면 2^(h+1) -1이다.

따라서, n개의 노드를 저장할 수 있는 완전 트리의 높이는 log n으로 표현할 수 있다.