트리(Tree)

트리 (Tree)

정점(node)과 간선(edge)을 이용하여 데이터의 배치를 나타내는 자료 구조

 

 

 

노드의 개념

 

루트(root)노드: 맨 위에서 시작되는 최초의 노드

리프(leaf)노드: 맨 아래에 위치하고 자식이 없는 말단 노드

부모(parent)노드: 루트 노드에 더 가까우며 자식을 가진 노드

자식(child)노드: 루트 노드로부터 더 멀고 부모를 가진 노드

형제(sibling)노드: 같은 부모를 둔 같은 레벨(level)의 노드들

조상(ancestor)노드: 부모를 비롯한 간선으로 이어진 루트 노드까지의 모든 부모 노드들

후손(descendant)노드: 자식을 비롯한 간선으로 이어진 리프 노드까지의 모든 자식 노드들

 

노드의 수준(level): 보통은 루트 노드의 레벨을 0으로 둔다.

루트 노드의 레벨을 0으로 두면 말단 노드까지 거쳐야하는 간선의 수를 계산하기 쉽다.

노드의 높이(Height): 트리의 높이로 '최대 레벨+1'이다. 깊이(depth)라고도 한다.

 

서브 트리(subtree): 트리에서 특정 노드를 선택해 그 이하의 모든 후손 노드 모음

 

노드의 차수(Degree): 특정 노드의 자식의 수(후손이 아님에 주의)

리프노드는 당연히 차수가 0이다.

 

 

 

 

이진 트리 (Binary Tree)

모든 노드의 차수가 2이하인 트리

주의할 점은 차수가 0인 말단 노드도 이진트리로 간주해야 재귀적으로 접근할 때 Stack Overflow Error를 피할 수 있다.

 

 

 

 

포화 이진 트리 (Full Binary Tree)

모든 레벨에서 모든 노드들이 채워져 있는 이진 트리

높이가 k이고 노드의 개수가 2**k-1인 이진트리로 2**k에 -1이 붙는 이유는 루트 노드 1개로 시작하기 때문

 

 

 

완전 이진 트리 (Complete Binary Tree)

높이가 k인 완전 이진 트리는

 

레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리면서

레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리를 말한다.

 

 

 

 

 

 

 

 

이진 트리의 순회 (Traversal)

 

깊이 우선 순회 (depth first traversal)

 

중위 순회 (in-order traversal)

왼쪽 서브 트리, 자신, 오른쪽 서브 트리

전위 순회 (pre-order traversal)

자기 지신, 왼쪽 서브 트리, 오른쪽 서브 트리

후위 순회 (post-order traversal)

왼쪽 서브 트리, 오른쪽 서브 트리, 자기 자신

 

 

 

 

 

넓이 우선 순회 (breadth first traversal)

수준 (level)이 낮은 노드를 우선으로 방문한다.

 

그렇다면 수준이 같은 노드들 사이에는?

부모 노드가 먼저 방문된 노드들을 먼저 방문하고

왼쪽 자식 노드를 오른쪽 자식 노드보다 먼저 방문 한다.

 

깊이 우선 순회에서 재귀를, 넓이 우선 순회에서는 큐를 사용

 

 

 

 

 

 

 

이진 탐색 트리 (Binary Search Trees)

모든 노드에 대해서

왼쪽 서브트리에 있는 데이터는 모두 현재의 노드 값보다 작고

오른쪽 서브트리에 있는 데이터는 모두 현재의 노드 값보다 큰

성질을 만족하고 계속 보장하는 이진 트리

 

 

장점

데이터 탐색에 매우 유리하다. 자료 구조의 특성상 매 순간(노드)마다 노드의 값을

비교해 양자택일만 하면 되므로 시간 복잡도가 밑이 2인 로그이기 때문이다.

 

단점

트리는 왼쪽 서브트리, 오른쪽 서브트리를 기억해야 하므로 공간복잡도가 높다.

 

주의점

모든 연산에 대해 밑이 2인 로그 시간복잡도인 것은 아니다.

 

 

 

 

이진 탐색 트리의 추상적 자료 구조

이진 탐색 트리의 각 노드를 (key, value) 쌍으로 두어

키로 검색 혹은 (점수, 사람 이름)으로 다양한 용도로 확장 가능

 

insert(key, data): key를 이용해 data를 트리에 삽입

remove(key): key에 해당되는 데이터를 트리에서 삭제

lookup(key): key에 해당되는 데이터를 검색

 

inorder(): 키의 순서대로 데이터를 나열

이진 탐색트리의

왼쪽 서브트리에 있는 데이터는 모두 현재의 노드 값보다 작고

오른쪽 서브트리에 있는 데이터는 모두 현재의 노드 값보다 큰 성질을 고려하면

중위탐색(inorder)으로 탐색해야 키의 순서대로 데이터가 나옴을 그림을 그리며 생각 해보자

 

min(), max(): 최소 키, 최대 키를 가지는 원소를 탐색

 

 

 

 

 

이진 탐색 트리가 비효율적인 경우

트리가 일렬로 쭉 뻗어있는 경우로 선형 탐색과 다를게 없다.

이진탐색트리의 효율성은 왼쪽과 오른쪽 서브트리가 균형있게 구성될수록 극대화 된다.

O(log n)이 보장된다