1. 트리의 개념과 구성요소
-
트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 구조이다.
-
계층적 관계를 표현한다.
-
Node: 트리를 구성하는 각각의 요소
-
Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선
-
Root Node(루트 노드): 부모가 없는 최상위에 있는 노드
-
Terminal Node(= Leaf Node, 단말 노드): 하위에 다른 노드가 연결되어 있지 않은 노드
-
Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드로, 루트 노드도 포함된다.
-
크기: 트리에 포함된 모든 노드의 개수이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개이다.
-
깊이: 루트 노드로부터의 거리
-
높이, 레벨: 각 층별로 숫자를 매겨서 이를 트리의 레벨이라 한다. 레벨은 1부터 시작하고 루트 노드의 레벨은 1이다. 그리고 트리의 최고 레벨을 가리켜 트리의 높이라고 한다.
-
차수: 각 노드의 자식 방향의 간선 개수
2. 이진 트리(Binary Tree)
2.1. 이진트리란?
이진 트리는 모든 노드들이 둘 이하(0, 1, 2개)의 자식을 가진 트리이다.
2.1. 이진 트리의 종류
이진 탐색 트리(Binary Search Tress, BST)
이진 트리 중, 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리이다(왼쪽 자식 노드의 값 < 부모 노드의 값 < 오른쪽 자식 노드의 값). 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.
이진 탐색 트리는 삽입, 삭제, 탐색의 과정에서 모두 트리의 높이만큼 탐색하기 때문에 O(logN)의 시간 복잡도를 갖는다.
전 이진 트리(Full Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는 구조이다.
완전 이진 트리(Complete Binary Tree)
마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 구조이다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져 있어야 한다. 즉 왼쪽이 비어있고 오른쪽이 채워진 트리는 완전 이진 트리가 아니다.
포화 이진 트리(Perfect Binary Tree)
모든 노드의 레벨이 동일하고, 모든 레벨이 가득 채워진 구조이다. 즉 모든 노드가 두 개의 자식 노드를 가지며, 모든 노드가 동일한 깊이 또는 레벨을 갖는다.
포화 이진 트리는 완전 이진 트리이기도 하다.
균형 이진 트리(Balanced Binary Tree)
왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리이다.
2.2. 이진 트리의 순회
트리의 순회는 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미한다.
-
전위 순회(Preorder): 루트를 먼저 방문한다. (부모 → 왼쪽 자식 → 오른쪽 자식)
-
중위 순회(Inorder): 왼쪽 자식을 방문한 뒤에 루트를 방문한다. (왼쪽 자식 → 부모 → 오른쪽 자식)
-
후위 순회(Postorder): 오른쪽 자식을 방문한 뒤에 루트를 방문한다. (왼쪽 자식 → 오른쪽 자식 → 부모)
-
레벨 순회: 부모 노드부터 계층 별로 방문하는 방식이다.
-
전위 순회: 1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14
-
중위 순회: 8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7
-
후위 순회: 8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
-
레벨 순회: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14
참고 자료
