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

 

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

 

 

 

트리(Tree)란?

 

 

 

트리(Tree)는 계층적인 자료를 표현하는 데 이용되는 자료구조이며, 컴퓨터의 directory를 예시로 들 수 있다.

 

실제 나무를 거꾸로 한 것과 같은 모양을 하고 있어 '트리'라고 부른다.

 

트리 관련 용어

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

이진트리(Binary Tree)

 

 

 

 

 

트리를 구성하는 노드의 branch 개수는 0개, 1개, 2개, 3개,... 등 여러 개가 될 수 있지만, 이진트리는 다르다.

 

이진트리는 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리로, 서브 트리 또한 모두 이진트리이다. 즉, branch가 최대 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로 값이 더 크다.

 

또한, 부모 노드를 중심으로 작은 값은 왼쪽 자식 노드에 큰 값은 오른쪽 자식 노드에 존재해야 하므로, 이진 탐색 트리의 모든 노드의 데이터 값은 중복되는 값이 존재하면 안 된다. 즉, 데이터 값은 유일해야 한다.

 

이진 탐색 트리 간단 정리

• 부모 노드보다 왼쪽 자식의 노드가 작다.
• 부모 노드보다 오른쪽 자식의 노드가 크다.
• 같은 데이터 값을 가지는 노드는 없다. (데이터 중복 X)