Tree(트리) 자료구조

트리(Tree)

트리(Tree)란 무엇일까?

자료구조, 코딩문제 등을 보다보면 트리라는 말이 자주 들린다.
트리는 노드(Node)란 것으로 이루어진 자료구조이며 다음과 같은 개념으로 정리된다.

- 노드들 간에 1:N 관계를 가지는 비선형 자료구조
- 원소들 간에 계층관계를 가지는 계층형 자료구조 
- 상위 원소에서 하위 원소로 내려가면서 확장되는 자료구조

처음 트리를 접한다면 무슨 말인지 이해가 잘 안갈 수 있으니 다음 그림을 보면서 함께 이해해 보자!!

나무(Tree) 그림이다. 큰 줄기에서부터 시작해서 가지를 거쳐 나뭇잎들을 가지고 있다.
트리 자료구조는 나무와 같은 모양이라 "Tree"라는 이름이 붙혀졌다. 용어들도 실제 나무가 가지고 있는 것과 거의 일치한다.

실제 자료구조에서 좀 더 이해하기 쉽도록 나뭇잎들은 없애고 좀 다듬어 보겠다.

우리가 앞으로 자주 보게될 트리의 모습이다. 각 용어들에 설명은 다음과 같다.

트리 용어

대표적인 트리의 용어들에 대하여 간략히 설명하자면 다음과 같다.

• 노드(Node) : 트리의 원소들 (A~F 까지 모두 노드들이다.)
• 루트노드(Root Node) : 트리의 시작에 있는 노드 (여기에서 A가 루트노드이다.)
• 간선(Edge) : 노드들을 연결하는 선
• 부모노드 : 각 노드에 대해 바로 상위 계층에 있는 간선으로 연결된 노드
• 자식노드 : 각 노드에 대해 바로 하위 계층에 있는 간선으로 연결된 노드
• 형제노드(Sibling Node) : 같은 부모 노드의 자식 노드들
• 리프노드(Leaf Node) : 자식노드가 없는 노드(여기에서는 D,E,F)
• 노드의 레벨(Level) : 특정 트리의 깊이를 가지는 노드의 집합(Level 1의 노드들 : B,C)
• 트리의 차수(Degree) : 노드에 연결된 자식 노드의 수

트리의 특징

트리는 그래프의 한 종류이기 때문에 트리를 만족하려면 다음과 같은 조건이 필요하다.

• 트리의 서로다른 두 노드에 대한 경로는 유일하다.
• 트리에는 반드시 한개의 루트노드(Root Node)만 존재하여야 한다.
• 트리에는 내부에 사이클이 존재해서는 안된다.

만약에 위 조건들을 만족하지 않는다면 그것은 트리가 아니라 그래프로 분류되어야 할 것 같다.

트리의 종류

트리의 종류는 굉장히 다양하다. 트리에 노드가 어떤식으로 놓이는지와 자식노드의 갯수로 나눠지게 된다.
가장 대표적인 이진트리의 종류들에 대해서 공부해 보도록 하자.

이진트리 (Binary Tree)

이진트리는 트리의 모든 노드의 차수를 2이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 하는 트리이다.
즉, 자식노드의 갯수가 최대 2개이다.

위 사진처럼 일반트리의 자식의 갯수가 자유롭지만 이진트리의 경우 2개 이하이여야 한다.

이러한 이진트리에도 다양한 종류가 있다.

• 포화 이진 트리 (Perfect Binary Tree )
  모든 레벨에 노드가 포화상태로 꽉 차있는 이진트리
  

• 완전 이진 트리 (Complete Binary Tree)
  트리의 마지막 레벨을 제외하고는 포화 이진 트리인 것이다.
  트리의 마지막 레벨을 체울 적엔 가장 왼쪽에서 오른쪽으로 채워져애 한다.
  

• 편향 이진 트리 (Skewed Binary Tree)
  모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 자식 노드를 가지고 있는 트리
  

• 이진 탐색 트리 (Binary Search Tree)
  이진 트리를 탐색용 자료구조로서 사용하기 위해 원소 크기에 따라 노드의 위치를 정한 것 입니다.
  이진 탐색 트리는 다음과 같은 조건들을 만족해야 합니다.

  • 모든 원소는 서로 다른 유일한 키를 갖는다.

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

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

  • 왼쪽 서브트리와 오른쪽 서브트리 또한 이진 탐색 트리이다.

    이진 탐색 트리를 통해 찾고자 하는 원소를 보다 빠르고 효율적으로 찾거나 추가 할 수 있는 장점이 있다.

• 힙(Heap)
  완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기
  위해서 만든 자료구조이다.

  • 최대힙 : 루트노드에 가장 큰 값이 들어간다. -> 가장 큰 값을 찾기에 용이하다.
  • 최소힙 : 루트노드에 가장 작은 값이 들어간다. -> 가장 작은 값을 찾기에 용이하다.

이진트리의 순회

트리에 있는 모든 원소를 빠트리거나 중복하지 않고 처리하기 위해 순회의 개념이 생겨났다.
이진트리의 순회에는 3가지 종류가 있으며 다음과 같이 노드를 처리한다.
(D : 현재 노드 작업, L : 왼쪽 노드 작업, R : 오른쪽 노드 작업)

• 전위 순회 : D -> L -> R
• 중위 순회 : L -> D -> R
• 후위 순회 : L -> R -> D

정리하면서

코딩테스트 문제에서 어려움을 겪었던 트리의 개념이 조금은 잡힌것 같다.
직접 하나하나 구현해 보면서 더욱더 기본 개념을 익혀야 겟다는 생각이 든다.

참고한 글들
http://www.ktword.co.kr/abbr_view.php?m_temp1=5424
https://futurists.tistory.com/59
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html