자료구조 트리(Tree)

트리란?

트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다.

 

트리관련용어

• 루트 노드(root node) : 부모가 없는 최상위 노드를 의미한다. 위 그림에서는 A이다.
• 단말 노드(leaf node) : 자식이 없는 노드. 위 그림에서는 G,H,E,I 이다.
• 크기(size) : 트리에 포함된 모든 노드의 개수. 위 그림에서는 9이다.
• 깊이(depth) : 루트 노드부터의 거리. 위 그림에서 B의 깊이는 1이다. D의 깊이는 2이다.
• 높이(height) : 깊이 중 최댓값. 위 그림에서는 G,H,I의 깊이는 3이다.
• 차수(degree) : 각 노드의 (자식 방향) 간선 개수

기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 개이다.

 

이진 탐색 트리 (Binary Search Tree)

사진출처 유튜브'동빈나'

• 이진 탐색이 실행될 수 있도록 만들어진 효율적인 탐색이 가능한 자료구조이다.
• 이진 탐색 트리의 특징은 왼쪽 자식노드 < 부모 노드 < 오른쪽 자식 노드 형태로 되어있다.
  • 부모 노드보다 왼쪽 자식 노드가 작고
  • 부모 노드보다 오른쪽 자식 노드가 크다.

이진 탐색이 효율적인 이유를 예를 들어서 생각해보자.

 

위 그림에서 찾고자 하는 값이 37이라고 가정했을 때, 30 -> 48 -> 37 이렇게 간단하게 찾을 수 있고, 이 과정에서 30의 왼쪽 자식 노드인 17과 연관된 노드들은 아예 탐색을 안해도 된다는 점이다.

 

이진 탐색에서의 삽입 및 삭제

 

이진 탐색에서 삽입을 할 때는 왼쪽 자식 노드는 부모 노드보다 무조건 작은 수를, 오른쪽 자식 노드에는 부모 노드보다 무조건 큰 수를 삽입 해주면 간단하다.

 

이진 탐색에서 삭제를 할 때는 3가지로 구분 될 수 있다.

• 자식 노드가 없는 노드를 삭제할 때.
  • 그냥 노드를 삭제해주면 된다.
• 왼쪽 자식 노드가 있는 부모 노드를 삭제할 때.
  • 왼쪽 자식 노드의 부모 노드를 삭제하고 왼쪽 자식 노드를 부모 노드의 부모 노드,  즉 할아버지(?) 노드에 연결해 준다.
• 왼쪽, 오른쪽 자식 노드 모두 있는 부모 노드를 삭제할 때.
  • 부모 노드를 삭제하고, 부모노드의 오른쪽 자식 노드에 있는 가장 왼쪽 자식 노드를 그 자리에 붙여주면 된다.

 

트리의 순회(Tree Traversal)

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 무조건 방문하는 방법을 의미한다.
  • 트리의 정보를 시각적으로 확인할 수 있다.
• 대표적인 트리 순회 방법은 세 가지가 있다.
  • 전위 순회 : 루트를 먼저 방문한다.
  • 중위 순회 : 왼쪽 자식을 방문한 뒤에 루트를 방문한다.
  • 후위 순회 : 오른쪽 자식을 방문한 뒤에 루트를 방문한다.

사진출처 유튜브'동빈나'

위와 같은 트리를 예로 생각해보자.

• 전위 순회 : A - B - D - E - C - F - G
• 중위 순회 : D - B - E - A - F - C - G
• 후위 순회 : D - E - B - F - G - C - A