트리(Tree)

트리(Tree)의 개념

트리는 노드(node)들을 간선으로 연결한 계층형 자료구조(hierarchical data structure)를 의미한다.

따라서 이 트리는 제일 위에 하나의 노드를 루트(root)로 하여 나머지 노드들이 간선으로 연결되어 있다.

 

트리는 다음과 같이 순환적으로 정의할 수 있다.

• 노드(node)들과 노들을을 간선들로 구성되어 있다.
  • 트리에는 사이클(Cycle)이 존재할 수 없다.
  • 노드들은 특정 순서로 나열될 수 있고 그럴 수 없을 수도 있다.
  • 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
  • 각 노드는 어떤 자료형으로도 표현 가능하다.
• 비선형 자료구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도
• 그래프의 한 종류
  • 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
  • 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프) 의 한 종류 이다.

트리 용어

A는 차수 2, E의 차수 1, F는 차수 0 단말노트, 잎노드

• 루트 노드(root node) : 부모가 없는 노드 , 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node) : 자식이 없는 노드, '말단 노드' 또는 '잎 노드' 라고도 부른다.
• 내부(internal) 노드 : 단말 노드가 아닌 노드
• 간선(edge)  : 노드를 연결하는 선(link,branch 라고도 부름)
• 형제(sibling) : 같은 부모를 가지는 노드
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 갯수
• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노트의 집합
• 노드의 차수(degree) : 하위 트리 개수/ 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree if tree) : 트리의 최대 차수
• 트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리(Tree)의 특징

• 그래프의 한 종류이다. '최소 연결 트리' 라고도 부른다.
• 트리는 계층 모델이다.
• 트리는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프) 의 한 종류 이다.
  • loop나 circuit이 없다. 당연히 self-loop도 없다.
  • 즉, 사이클이 없다.
• 노드가 N개인 트리는 항상 n-1개의 간선(edge)을 가진다.
  • 즉, 간선은 항상(정점의 개수 - 1 ) 만큼을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  • 임의의 두 노드 간의 경로도 유일하다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한 개의 루트 노드 만이 존재하며 모든 노드 자식 노드는 한개의 부모 노드만을 가진다.
  • 부모 - 자식 관계이므로 흐름은 top-bottom 아니면 bottom - top으로 이루어진다.
• 순회는 Pre-order(전위) , In-order(중위) 아니면 Post-order(후위)로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
• 트리는 이진 트리 , 이진 탐색트리 , 균형 트리(AVL 트리, Red-Black트리), 이진 힙(최대힙, 최소힙)등이 있다.

트리의 종류

이진트리

이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있는 트리이다.

단, 서브트리는 공백(empty)이 될 수 있다. 두 공백 서브트리(Empty Subtree)를 가지고 있는 노드를 리프 노드(leaf node)라 한다.

노드의 서브트리 수에 제약이 없는 일반 트리에서는 서브트리의 순서를 구별하지 않지만 이진 트리에서는 왼쪽 서브트리와 오른쪽 서브트리를 분명하게 구별한다.

 

이진 트리의 정의

이진 트리(binary tree : BT)는 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진 트리인 왼쪽 서브트리와 오른쪽 서브트리로 구성된다.

 

트리 VS 이진 트리

• 이진 트리(Binary Tree)
  • 각 노드가 최대 두 개의 자식을 갖는 트리
  • 모든 트리가 이진 트리는 아니다.
  • 이진 트리 순회
    1. 중위 순회(In-order Traversal) : 왼쪽 가지 > 현재 노드 > 오른쪽 가지
    2. 전위 순회(Pre-order Traversal) :  현재 노드 -> 왼쪽 가지  > 오른쪽 가지
    3. 후위 순회(Post-order Traversal) : 왼쪽 가지 > 오른쪽 가지 > 현재 노드

 

 

 

 

이진 탐색 트리

이진 트리 구조를 가진 이진 탐색 트리는 임의의 키를 가진 원소를 삽입 , 삭제 , 검색하는데 효율적인 자료구조다.

실제 이진 탐색 트리에서의 연산은 모두 키 값을 기초로 실행된다.

 

이진 탐색 트리 정의

이진 탐색 트리(Binary search Tree : BST)는 이진 트리로서 공백이 아니면 다음 성질을 만족한다.

1) 모든 원소는 상이한 키를 갖는다.

2) 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.

3) 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.

4) 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리이다.

 

이진 탐색 트리는 b,c

위 그림에서 a는 이진 탐색 트리 정의 1,2,3을 만족하지만 4를 만족하지 않기 때문에 이진 탐색 트리가 아니다.

b와 c는 1,2,3,4 를 모두 만족하기 때문에 이진 탐색 트리이다.

 

이진 탐색 트리의 검색

이진 탐색 트리는 순환적 정의를 가지고 있기 때문에 탐색도 순환적으로 기술하는 것이 편리하다.

 

키 값이 x인 원소를 탐색하는 경우를 생각하면 탐색은 루트로부터 시작하여 먼저 공백인가를 검사 후 공백이면 탐색 실패로 끝나고, 공백이 아니면 탐색을 계속한다.

 

루트의 키 값과 x를 비교하여 같으면 찾는 원소는 루트가 되어 탐색은 성공으로 종료한다.

 

키 값과 x가 루트의 키 값 보다 작으면 루트의 왼쪽 서브트리만 탐색하고 클 경우 오른쪽 서브트리만 탐색한다.

이 루트의 오른쪽 서브트리에 있는 원소틀의 키 값들은 모두 루트의 키 값보다 크고 왼쪽은 루트의 키 값보다 작기 떄문이다.

 

이진 탐색트리의 삽입

키 값이 x인 새로운 원소를 이원 탐색 트리에 삽입하기 위해서는 먼저 이진 탐색 트리에서 x를 키 값으로 가진 원소가 있는지 확인한다.

 이를 위해서는 탐색 키 값을 x로 하여 탐색을 수행한다. 만일 키 값 x를 가진 원소가 있어야 할 곳에 없어서 탐색이 실패하면 x를 키 값으로 가진 원소가 이진 탐색 트리에 없는 것이기 때문에 탐색이 종료된 지점에 원소를 삽입하면 된다.

 

이진 탐색트리의 삭제

주어진 키 값을 가진 원소를 삭제하려 할 때 제일 먼저 해야할 것은 이진 탐색 트리에서 이 키값을 가진 원소를 찾아내는 것이다.

만약 이 삭제할 원소를 성공적으로 찾으면 수행해야 될 삭제 연산은 이 원소가 가진 자식의 수(0,1,2)에 따라 경우가 나누어 진다.

 

1) 자식이 없는 리프 노드의 삭제

 

삭제해야 할 노드가 자식이 없는 리프 노드의 경우에는 부모 노드의 해당 링크 필드를 널(null)로 만들고 삭제한 노드를 반환하면 된다.

 

2) 자식이 하나인 노드의 삭제

 

삭제될 노드가 하나의 자식만을 가진 노드인 경우에는 삭제되는 노드의 자리에 하나밖에 없는 그 자식 노드를 위치시키면 된다.

 

2) 자식이 둘인 노드의 삭제

 

삭제 해야 될 노드가 두 자식을 가진 경우에는 먼저 삭제되는 그 노드 자리에 그의 왼쪽 서브트리에서 제일 큰 원소로 대체할 것인지 또는 오른쪽 서브트리에서 제일 작은 원소로 대체할 것인지 선택 후 해당 서브트리에서 이 대체 원소를 삭제하면 된다.

 

이진 탐색 트리에서 자식이 두개인 원소 삭제

균형 트리 vs 비 균형 트리

• 균형 트리
  • O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는경우 Ex) 레드-블랙 트리 , AVL 트리

완전 이진 트리 vs 전 이진 트리 vs 포화 이진 트리

 

• 완전 이진 트리(Complete Binary Tree)

 

• 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리, 즉, 마지막 레벨을 제외하고 모든 레벨이 꽉 채워져 있다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져 있어야한다.
• 마지막 레벨 h에서 (1 ~ 2h-1)개의 노드를 가질 수 있다.
• 또 다른 정의는 가장 오른쪽의 잎 노드가 제거된 포화 이진 트리다.
• 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

• 전 이진 트리(Full Binary Tree 또는 Strictly Binary Tree)
•  

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

• 포화 이진 트리(Perfect Binary Tree)
•  

• 전 이진 트리이면서 완전 이진 트리인 경우
• 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.
• 모든 내부 노드가 두 개의 자식 노드를 가진다.
• 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
• 노드의 개수가 정확히 2^(k-1)개여야 한다. (k : 트리의 높이) -> 흔하게 나타나는 경우가 아니다. 즉, 이진 트리가 모두 포화 이진 트리는 아니다.

이진 힙(최소 힙과 최대힙)

• 최소힙(Min Heap)
  • 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 이진 트리이며, 각 노드의 원소가 자식들의 원소보다 작다.
    • 즉, key(부모 노드) >= key(자식 노드)인 완전 이진 트리
    • 가장 큰 값은 루트 노드이다.
    • N개가 힙에 들어가 있으면 높이는 log(N)이다.
• 최대힙(Max Heap)
  • 원소가 내림차순으로 정렬되어 있다는 점에서만 최소힙과 다르다.
  • 각 노드의 원소가 자식드르이 원소보다 크다.

 

트리(Tree)의 구현 방법

기본적으로 트리는 그래프의 한 종류이므로 그래프의 구현 방법(인접 리스트 또는 인접 배열)으로 구현 할 수 있다.

 

인접 배열 이용

1.  1차원 배열에 자신의 부모 노드만 저장하는 방법
   • 트리는 부모 노드를 0개 또는 1개를 가지기 때문
   • 부모 노드를 0개 : 루트 노드
2. 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
   • 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
   • Ex) A[i][o] : 왼쪽 자식 노드 , A[i][1] : 오른쪽 자식 노드

인접 리스트 이용

1. 가중치가 없는 트리의 경우
   • ArrayList < ArrayList > list = new ArrayList<>();
2. 가중치가 있는 트리의 경우
   • 1) class Node{int num , dist // 노드 번호 , 거리 } 정의
   • 2) ArrayList[] list = new ArrayList[정점의 수 + 1];

 

 

그래프와 트리의 차이

 

 

참고 

gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

참고 도서 : 자료구조와 C