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

 

이번에는 자료구조 중 하나인 트리(Tree)에 대해서 정리하겠습니다.
가급적이면 쉽고 간단하게 설명할 예정이며, 더 깊고 많은 내용을
알고 싶으시다면 다른 블로그를 참고하시기 바랍니다 :)

 

 

 

트리(Tree)란?

 

 

 

트리(Tree)는 계층적인 자료를 표현하는 데 사용되는 자료구조입니다. 

가장 대표적인 예시로는 컴퓨터의 디렉토리 구조를 예시로 들 수 있습니다.

 

실제 나무를 거꾸로 놓은 것과 비슷한 형태를 가지고 있기 때문에 '트리(Tree)'라고 부릅니다.

 

트리 관련 용어

• 루트 노드(root node): 부모가 없는 최상위 노드 (A)
• 단말 노드(leaf node): 자식이 없는 노드 (H, I, E, J, G)
• 크기(size): 트리에 포함된 모든 노드의 개수 
• 깊이(depth): 루트 노드로부터의 거리 (A의 깊이는 0, A의 자식인 B와 C는 1, 그 아래 노드들은 2, ...)
• 높이(height): 트리의 깊이 중 최댓값(즉, 가장 깊은 노드의 깊이)
• 차수(degree): 각 노드가 가진 자식 노드의 개수(A는 B와 C로 나눠지므로 A의 차수는 2가 되며, E는 단말 노드이므로 차수는 0)

이진트리(Binary Tree)

 

 

 

 

 

트리의 각 노드는 여러 개의 자식을 가질 수 있지만, 이진 트리는 모든 노드가 최대 2개의 자식 노드(서브 트리)만 가지는 트리입니다.

 

또한, 이진 트리의 서브 트리도 모두 이진 트리입니다.

 

트리 순회

트리 순회란, 트리의 모든 노드를 특정한 순서로 한 번씩 방문하는 것을 의미합니다.

 

이를 통해서 트리의 구조를 파악하거나, 값을 읽어올 수 있습니다.

 

예시 트리에서 A -> B -> C 순으로 구성되어있다고 가정하면,

 

• 전위 순회(Pre-order traversal): 노드 -> 왼쪽 자식 -> 오른쪽 자식 순서로 방문하는 순회 방법 A -> B -> C
• 중위 순회(In-order traversal): 왼쪽 자식 ->노드 -> 오른쪽 자식 순서로 방문하는 순회 방법 B -> A -> C
• 후위 순회(Post-order traversal): 왼쪽 자식 -> 오른쪽 자식 -> 노드 순서로 방문하는 순회 방법 B -> C -> A

 

 

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

 

 

 

 

 

이진 탐색 트리는 위에서 설명한 이진 트리에 조건이 추가된 구조입니다.

 

예를 들어, 위 이미지에서 부모 노드인 10을 기준으로 보면,

왼쪽 자식 노드인 7은 더 작고, 오른쪽 자식 노드인 14는 더 큽니다.

 

또한, 7을 기준으로 봐도 

왼쪽 자식 노드는 1로 더 작고, 오른쪽 자식 노드는 9로 더 큽니다.

 

이처럼 이진 탐색 트리는 모든 노드가 '왼쪽 < 부모 < 오른쪽'의 규칙을 만족해야합니다.

 

또한, 같은 값을 가진 노드는 허용되지 않으며, 모든 노드의 값은 유일(unique)해야 합니다.

 

이진 탐색 트리 간단 정리

• 부모 노드보다 왼쪽 자식의 값이 작다.
• 부모 노드보다 오른쪽 자식의 값이 크다.
• 중복된 값은 존재하지 않는다. (데이터 중복 X)