트리
비순차적 자료 구조인 트리는 계층 구조를 추상화한 모델이다.
트리는 그 모양이 뒤집어 놓은 망과 비슷하다고 해서 이런 이름이 붙었다.
트리는 부모 - 자식 관계를 가진 다수의 노드로 구성된다.
각 노드는 부모 노드를 가지며(최상위 노드를 제외하고) 다수 자식 노드를 가질 수 있고 하나도 없을 수도 있다.
- 노드 : 트리의 원소는 노드라고 부르는데, 보통 데이터가 담긴다.
- 내부 노드 : 1개 이상의 자식을 가진 노드
- 외부 노드(리프 노드) : 자식이 하나도 없는 노드를 외부 노드 또는 리프라고도 한다.
- 루트 : 트리에서 최상위 노드는 루트라고 하며, 부모가 없는 노드이다.
- 간선(edge) : 루트와 서브트리를 연결하는 선
- 차수 : 노드가 가지고 있는 자식 노드의 개수
- 깊이 : 노드의 깊이란 조상의 개수를 말한다.
- 높이 : 루트 노드에서 말단 노드에 이르기까지 깊이의 최대치다. 트리가 가지고 있는 최대 레벨이라 할 수 있다.
특정 깊이를 가지는 노드들의 집합을 레벨이라고 부른다.
- 루트는 레벨 0, 그 하위 지식은 레벨 1
- 경로 : 인접한 노드들로 이뤄진 시퀀스, 경로의 길이는 경로에 속한 엣지의 수로 나타낸다.
- 트리의 속성 중 가장 중요한 것은 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 가진다는 것이다.
트리의 성질 및 특징
루트노드를 제외한 모든 노드는 단 하나의 부모 노드만을 가짐으로 나오는 트리의 성질 및 특징을 알아보자
- 그래프의 한 종류이다. '최소연결 트리'라고도 불린다.
- 트리는 계층 모델이다.
- 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지를 하나 자르면 트리가 두개로 분리된다.
- 엣지의 수는 노드의 수에서 1을 뺀것과 같다.(엣지 = 노드 - 1)
이진트리(Binary Tree)란?
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리이다. 이진트리에는 정이진트리, 완전 이진트리, 균형 이진트리 등이 있다.
이진 트리에서 노드는 좌, 우측에 각각 하나씩, 최대 2개의 자식 노드를 갖는다 따라서 노드의 삽입, 조회, 삭제를 효과적으로 수행할 수 있어서 컴퓨터 과학에서 아주 폭넓게 활용된다.
종류
-
정 이진트리 : 모든 레벨에서 노드들이 꽉 채워진(잎새 노드를 제외한 모든 노드가 자식 노드를 2개 가진다) 이진트리이다.
-
완전 이진트리 : 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리로, 각 노드에 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있다. 부여된 번호는 항상 일정하다.
-
균형 이진트리 : 모든 잎새노드의 깊이 차이가 많아야 1인 트리를 말한다. 예측가능한 깊이를 가지며, 노드가 n개인 군형 이진트리의 깊이는
log n을 내림한 값이 된다.
정 이진트리와 완전 이진트리는 1차원 배열로도 표현이 가능하다.
- 어떤 노드의 인덱스를 index, 왼쪽 자식 노드의 인덱스를 left index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면
left_index = 2 * index + 1 right_index = 2 * index + 2
성질
- n개의 노드를 가진 이진 트리는 n-1개의 간선을 가진다.
부모 - 자식 간 간선은 1개씩 존재하는데, 루트 노드는 부모 노드가 없으므로 노드 개수보다 간선이 1개 적다.
- 높이가h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가진다.
한 레벨에 최소 하나의 노드는 존재해야 하므로, 최소 노드를 가지는 경우 높이만큼의 노드를 가진다.
- n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 최소 ┌log₂(n+1)┐이 된다.
앞서 설명한 것처럼 한 레벨에 최소 하나의 노드가 존재하므로 최대 높이는 n이다. 마찬가지로, 높이 h의 이진 트리가 가지는 최대 노드 개수는 2^h-1이다.
표현
1. 배열 표현법
배열을 이용하는 방법은 주로 포화 이진 트리나 완전 이진 트리의 경우 많이 쓰인다. 이외 이진 트리도 저장이 불가능한 것은 아니지만 그림에서 볼 수 있는 것처럼 중간중간 빈 곳이 있어 메모리 공간의 낭비가 발생한다.
2. 링크 표현법
링크 표현법에서는 노드가 구조체로 표현되고, 각 노드가 가진 포인터를 이용해 노드와 노드를 연결하는 방법이다. 이진 트리를 링크 표현법으로 표현하면, 데이터 필드 1개와 양쪽 자식 노드 각각을 가리키는 2개의 포인터 필드를 가진다.
트리순회(tree traversal)
이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.
트리를 사용하는 목적은 트리의 노드에 자료를 저장하고 필요에 따라서 이 자료를 처리하기 위함이ㅏㄷ.
따라서, 트리가 가지고 있는 자료를 순차적으로 순회하는 것은 이진 트리에서 중요한 연산이다.
스택이나 큐는선형적으로 자료를 저장하기 때문에 순회하는 방법이 하나(선입후출 / 선입선출) 뿐이었지만, 트리는
여러가지 순서로 자료에 접근할 수 있다.
노드를 방문하는 순서에 따라 전위 순회(preorder) 중위 순회(inorder), 후위 순회(postorder) 세가지로 나뉜다.
- preorder : 루트 노드에서 시작해서 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal) 라고도 한다.
1 → 2 → 4 → 5 → 3 - inorder : 루트 노드에서 시작해서 왼쪽 서브 트리 노드 → 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)이라고도 불린다.
4 → 2 → 5 → 1 → 3 - postorder : 루트 노드에서 시작해서 왼쪽 서브트리 → 오른쪽 서브트리 → 노드 순으로 순회하는 방식
4 → 5 → 2 → 3 → 1
참조
https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14
