210624 트리(Tree)

트리(Tree) : 계층적인 구조, 노드들로 구성됨, 노드들이 부모 자식 관계 가짐

 

트리의 용어

• 노드(node) : 트리의 구성요소
• 루트(root) : 부모가 없는 노드
• 서브트리(subtree) : 하나의 노드와 그 노드들의 자식들로 이루어진 트리
• 단말노드(terminal node) : 자식이 없는 노드
• 비단말노드(non-terminal node) : 적어도 하나의 자식을 가지는 노드
• 레벨(level) : 트리의 각층의 번호
• 높이(height) : 트리의 최대 레벨
• 차수(degree) : 노드가 가지고 있는 자식 노드의 개수

 

이진 트리(binary tree) : 모든 노드가 2개의 서브 트리를 가지고 있는 트리

• 노드에는 최대 2개까지의 자식 노드 존재
• 모든 노드의 차수 2개 이하가 되어 구현하기 편리
• 노드의 개수가 n이면 간선의 개수는 n-1 
• 높이가 h 인 이진트리의 경우, 최소 h개의 노드를 가지며, 2^h-1개의 노드를 가짐

 

이진트리의 종류

• 포화 이진트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진트리
• 완전 이진 트리 : 높이 h일 때 레벨 1부터 h까지는 노드가 모두 채워져 있고 마지막 레벨 h에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리
• 편향 이진 트리 : 왼쪽 또는 오른쪽으로 편향되게 채워져 있는 트리, 각각의 레벨에서 1개의 노드만 있음
• 정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드만을 갖는 트리 
• 균형 이진 트리 : 모든 노드의 왼쪽과 오른쪽 서브트리의 높이가 1이상 차이나지 않는 트리

왼쪽부터 순서대로 포화 이진, 완전 이진, 편향 이진, 정 이진, 균형 이진 트리

 

 

 

이진트리의 표현으로 배열 표현법과 링크 표현법이 있음

배열 표현법은 모든 이진트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 이를 배열의 인덱스로 삼아 배열에 저장함

링크 표현법은 포인터를 이용하여 부모 노드가 자식 노드 가리키게 하는 방법

배열 표현법                                                                                링크표현법

 

이진트리의 순회 

전위 순회(preorder traversal) : 루트 -> 왼쪽 자식 -> 오른쪽 자식

중위 순회(inorder traversal) : 왼쪽 자식 -> 루트 -> 오른쪽 자식

후위 순회(postorder traversal) : 왼쪽 자식 -> 오른쪽 자식 -> 루트

 

이진탐색트리 : 탐색 작업을 효율적으로 하기 위한 자료구조 

key(왼쪽 서브 트리) <= key(루트 노드) <= key(오른쪽 서브 트리) 

이진탐색을 중위 순회로 하면 오름차순으로 정렬된 값을 얻을 수 있음

탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이 h에 비례한다. 

최선의 경우 h=log2(n) , 최악의 경우 h=n 으로 순차 탐색과 시간 복잡도가 동일