on
#6 트리(Tree) 1 - 트리의 개념/이진 트리
#6 트리(Tree) 1 - 트리의 개념/이진 트리
1. 트리(Tree)
트리는 그래프(Graph)와 유사한 형태를 가지며 어떤 의미로는 그래프의 일종이라고 볼 수도 있다.
다만 모든 노드가 동등한 관계였던 그래프와는 달리 트리의 노드는 서로 부모/자식의 관계를 가진다.
아래 예시를 보며 좀더 자세히 알아보자.
부모 노드를 가지지 않는 노드를 루트(root) 노드 라고 한다.
라고 한다. 루트 노드를 제외한 모든 노드는 한 개의 부모 노드를 가진다.(두 개 이상의 부모 노드를 가질 수 없다)
자식 노드를 가지지 않는 노드들을 리프(leaf) 노드 라고 한다.
라고 한다. 리프 노드를 제외한 모든 노드는 한 개 이상의 자식 노드를 가진다.
어떤 노드의 자식노드를 루트로 하는 트리를 그 노드의 서브 트리(subtree) 라고 한다.
라고 한다. 어떤 노드가 가지는 자식 노드의 갯수(혹은 서브트리의 갯수)를 노드의 차수(degree) 라고 한다.
트리 전체의 차수는 노드들의 차수 중 가장 큰 값이 된다.
라고 한다. 트리 전체의 차수는 노드들의 차수 중 가장 큰 값이 된다. 루트 노드로부터 어떤 노드 까지 거쳐야하는 간선의 갯수를 그 노드의 깊이(depth) 라고 한다.
루트 노드의 깊이는 0이다.
라고 한다. 루트 노드의 깊이는 0이다. 서로 깊이가 같은 노드들의 집합을 레벨(level) 이라고 한다. 위 트리에서의 레벨 1에 해당하는 노드는
3, 2, 0 이 있다.
2. 트리의 표현
배열을 사용한 트리의 표현 arr[0] 을 루트 노드로 한다 노드 arr[i] 의 좌측 자식 노드는 arr[i * 2 + 1], 우측 자식 노드는 arr[i * 2 + 2] 에 저장된다. 특수한 트리가 아니면 메모리의 낭비가 매우 심하다. 완전 이진 트리를 나타내는 경우라면 빈 공간이 없고 자식 노드를 가리키기 위한 포인터가
필요하지 않기 때문에 효율적이다.
연결 리스트를 사용한 트리의 표현 자기 자신의 데이터와 좌측, 우측 자식노드를 가리키는 포인터를 가지는 노드 간의 연결로 표현한다. 정확히 노드의 수 만큼만 메모리를 차지하기 때문에 대부분의 경우 배열을 사용한 방식보다
메모리 효율이 좋다. 특정 노드에의 접근이나 트리의 순회 등은 배열을 사용한 방식에 비해 느리다.
3. 트리의 순회(Traversal)
트리의 순회방법 네 가지에 대해 알아본다. 모든 순회는 루트 노드로부터 시작한다.
1) 전위 순회(Preorder Traversal)
절차
① 현재 노드를 탐색
② 좌측 자식 노드로 이동하여 해당 절차를 수행
③ 우측 자식 노드로 이동하여 해당 절차를 수행
① 현재 노드를 탐색 ② 좌측 자식 노드로 이동하여 해당 절차를 수행 ③ 우측 자식 노드로 이동하여 해당 절차를 수행 결과
4 - 2 - 3 - 5 - 7 - 1 - 9 - 8 - 6
4 - 2 - 3 - 5 - 7 - 1 - 9 - 8 - 6 순서의 맨 앞이 항상 루트 노드를 가리킨다.
일반적인 깊이 우선 탐색이 이와 같은 순서를 보인다.
2) 후위 순회(Postorder Traversal)
절차
① 좌측 자식 노드로 이동하여 해당 절차를 수행
② 우측 자식 노드로 이동하여 해당 절차를 수행
③ 현재 노드를 탐색
① 좌측 자식 노드로 이동하여 해당 절차를 수행 ② 우측 자식 노드로 이동하여 해당 절차를 수행 ③ 현재 노드를 탐색 결과
5 - 7 - 3 - 9 - 8 - 1 - 2 - 6 - 4
순서의 맨 뒤가 항상 루트 노드를 가리킨다.
3) 중위 순회(Inorder Traversal)
절차
① 좌측 자식 노드로 이동하여 해당 절차를 수행
② 현재 노드를 탐색
③ 우측 자식 노드로 이동하여 해당 절차를 수행
① 좌측 자식 노드로 이동하여 해당 절차를 수행 ② ③ 결과
5 - 3 - 7 - 2 - 9 - 1 - 8 - 4 - 6
루트보다 먼저 방문한 쪽은 좌측 서브트리에, 나중에 방문한 쪽은 우측 서브트리에 속한다
이진 탐색 트리를 중위 순회 할 경우 노드들을 오름차순 정렬한 순서로 방문하게 된다.
4) 레벨 순회(Level-order Traversal)
절차
① 현재 레벨의 모든 노드를 좌측부터 순서대로 순회
② 다음 레벨로 이동하여 해당 절차를 수행
① ② 결과
4 - 2 - 6 - 3 - 1 - 5 - 7 - 9 - 8
너비 우선 탐색이 이와 같은 순서를 보인다.
큐(Queue) 를 사용하여 구현할 수 있다.
4. 트리의 종류 - 이진 트리
1) 이진 트리(Binary Tree)
차수가 2인 트리, 즉 노드가 가질 수 있는 자식 노드의 최대 갯수가 2인 트리를 의미한다.
2) 이진 탐색 트리(Binary Search Tree)
어떤 노드의 좌측 서브 트리에는 자신보다 작은 값을 가지는 노드만이, 우측 서브 트리에는 자신보다 큰 값을
가지는 노드만이 존재하는 상태의 이진 트리이다.
가지는 노드만이 존재하는 상태의 이진 트리이다. 균형이 잘 잡힌 이진 탐색 트리의 경우 트리 내의 특정 데이터를 탐색하는데 O(logN) 의 시간복잡도를 보인다.
3) 완전 이진 트리(Complete Binary Tree)
트리 A 트리 B 트리 C
마지막 레벨을 제외한 레벨이 완전히 채워져있으며 마지막 레벨의 노드가 왼쪽에서부터 채워진 상태인
이진 트리이다.
이진 트리이다. 배열로 표현했을 때 빈 칸이 생기지 않는 트리이다.
위 그림에서 A는 완전 이진 트리지만 B는 레벨 2가 완전히 채워지지 않았기 때문에, C는 마지막 레벨의 노드 8, 9 가
왼쪽에서부터 채워지지 않았기 때문에 완전 이진 트리가 아니다.
4) 정 이진 트리(Full Binary Tree)
모든 노드가 자식노드를 두 개 가지거나 아예 가지지 않는, 즉 자식 노드를 하나만 가지는 노드가 없는 트리이다.
5) 포화 이진 트리(Perfect Binary Tree)
마지막 레벨까지 빈 공간 없이 완전히 채워진 이진 트리이다.
6) 균형 이진 트리(Balanced Binary Tree)
트리 A 트리 B
명확한 정의가 있는 것은 아니지만 트리 B와 같이 치우친 상태가 아닌 A와 같이 균형을 이룬 상태의
이진 트리이다.
이진 트리이다. 균형의 기준을 어떻게 세우느냐에 따라 다른 형태가 될 수 있지만 일반적으로는 모든 노드에 대해
좌측과 우측의 서브트리의 높이 차이가 일정이상 나지 않을 것을 기준으로 한다.
from http://scala0114.tistory.com/104 by ccl(A) rewrite - 2021-10-04 15:26:34