[자료구조] 자료구조 트리(Tree) 🌳

 

이번 글에서는 자료구조 트리(Tree)에 대해서 정리하겠습니다. 

트리란?

트리(Tree)는 컴퓨터 자료구조에서 계층적인 자료를 표현하는 데 있어 사용되는 자료구조입니다.

실제 나무를 거꾸로 한 것과 같은 모양을 하고 있어 트리(Tree)라고 표현합니다.

 

트리는 노드로 이루어진 자료구조

• 트리는 하나의 루트노드를 가진다.
• 각각의 간선은 방향성을 가지며, 부모는 자식에게만 연결가능하다.
• 루트 노드는 0개 이상의 자식 노드를 가지고 있다.
• 그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 이게 반복적으로 정의된다.
• 트리는 사이클(cycle)이 존재할 수 없다.

트리 관련 용어

• 간선(edge) : 노드와 노드를 연결하는 선
• 루트 노드(root node) : 부모가 없는 최상단에 위치하는 노드 (A)
• 단말 노드(leaf node) : 자식이 없는 노드 (H, I, E, J, G)
• 형제 노드(sibling node) : 같은 부모를 가지는 노드 (B, C), (D, E)
• 크기(size) : 트리에 포함된 노드의 개수 (10)
• 깊이(depth) : 루트 노드로부터의 거리 (A는 루트노드 이므로 0, 그 밑에 B와 C로 나누어지니 B와 C의 깊이는 1, 그 아래 D, E, F, G는 높이가 2)
• 높이(heigh) : 깊이 중 최댓값
• 차수(degree) : 각 노드의 간선 개수(A는 B와 C로 나눠지니까 A의 차수는 2가 됩니다.)

이진트리(Binary Tree)

트리를 구성하는 노드의 branch 개수는 여러 개가 될 수 있지만, 이진트리는 다릅니다.

 

이진트리는 모든 노드가 최대 2개의 서브 트리를 가지고 잇는 트리로, 서브 트리 또한 모두 이진트리입니다.

 

완전 이진 트리 (Complete Binary Tree)

 

완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있습니다. 

마지막 레벨을 다 채워지지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 합니다.

 

전 이진 트리 (Full Binary Tree)

전 이진트리는 모든 노드의 자식노드가 0개 아니면 2개를 가지는 것을 말합니다.

 

포화 이진 트리 (Perfect Binary Tree)

포화 이진 트리는 모든 레벨의 노드가 다 가득 차 있는 트리를 말합니다.

트리 순회

트리 순회란, 트리 자료구조에 포함된 노드들을 특정한 방법으로 한 번씩 방문하는 것을 말합니다.

• 전위 순회 : 노드, 왼쪽 자식, 오른쪽 자식 순서대로 방문하는 방법 A -> B -> C
• 중위 순회 : 왼쪽 자식, 노드, 오른쪽 자식 순서대로 방문하는 방법 B -> A -> C
• 후위 순회 : 왼쪽 자식, 오른쪽 자식, 노드 순서대로 방문하는 방법 B -> C -> A

이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리는 이진트리에서 조건이 더해진 자료구조라고 생각하면 됩니다.

 

이진 탐색 트리는 모든 노드가 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드의 순서대로 값이 커집니다.

 

위의 그림을 보면 부모 노드 10을 기준으로 왼쪽 자식 노드인 7이 10보다 작고 오른쪽 자식 노드인 14가 10보다 큽니다.

부모노드 7을 기준으로 봐도 왼쪽 자식인 1이 7보다 작고 오른쪽 자식인 9가 7보다 큽니다.

 

부모 노드를 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽에 존재해야 하므로, 이진 탐색 트리의 모든 데이터는 중복된 값이 존재하며 안됩니다. 하나의 트리에 존재하는 값들은 모두 유일해야 합니다.

 

Reference

• https://propercoding.tistory.com/214. 
• https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html