[CS] 4-3 자료구조. - 트리

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.

1. 트리

트리는 주로 계층적인 구조를 표현하기 위한 자료구조이다. 데이터가 저장되는 노드(node), 노드와 노드를 연결하는 간선(edge 혹은 link라고도 부른다.)으로 이루어져 있으며, 간선으로 연결된 노드는 상하 관계를 형성한다. 다양한 용어가 있는데, 차례대로 알아보자.

• 노드 간 형성된 상하 관계에서 상위는 부모 노드, 하위는 자식 노드라고 부른다.
• 두 개념 모두 상대적인 개념이기 때문에, 자식 노드이면서 부모 노드일 수 있다.
• 노드는 하나 이상의 자식을 가질 수 있지만, 부모 노드는 하나만 있을 수 있다.
• 형제 노드(sibling node) : 같은 부모 노드를 공유하는 노드를 의미한다.
• 조상 노드(ancestor node) : 특정 노드에 대해 부모 노드와 그 부모 노드들을 지칭한다.
• 자손 노드(descendant node) : 특정 노드에 대해 자식 노드와 그 노드의 자식 노드들을 지칭한다.
• 루트 노드(root node) : 부모 노드가 없는 최상단 노드
• 리프 노드(leaf node) : 자식이 없는 최하단 노드
• 차수(degree) : 각 노드가 가지는 자식 노드의 수
• 레벨(level) : 루트 노드에서 특정 노드까지 거치는 간선의 개수를 의미한다. 특정 노드가 얼마나 깊은 곳에 있는지를 뜻하는 트리의 깊이와 같은 개념이다.
• 레벨 중 가장 높은 레벨이 곧 트리의 높이다.
• 트리 안에 또 다른 트리 구조가 있을 수 있으며, 이를 서브트리(subtree)라고 한다.

 

위와 같은 내용이 트리라는 자료구조를 이해함에 있어 필수적인 내용이다. 양이 많아 보이지만 결국 하나하나 트리 구조에 대해서 학습하다 보면 익숙해질 내용이니 어려워할 필요 없다.

 

그렇다면 실제로 메모리 상에 어떻게 구현하고 저장할 수 있을까? 다양한 구현 방식이 있겠지만, 연결리스트와 유사하게 데이터를 저장할 공간 + 자식 노드의 위치 정보... 로 구성된다. 위치 정보는 자식 노드가 여러 개라면 그만큼 존재할 테니 하나는 아니다.

---

1-2 트리의 순회

트리의 모든 노드를 한 번씩 방문하는 것을 트리의 순회라고 부른다. 이런 트리의 순회 방식에는 크게 3가지가 있는데, 아래 트리 그림을 기준으로 차례대로 설명하면 다음과 같다.

순회는 처음에 이해하기 난해할지도 모르지만, 각각 순서가 어떤지 보고 난 뒤 차근차근 설명하도록 하겠다.

• 전위 순회 : A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> G
• 중위 순회 : H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> C -> G
• 후위 순회 : H -> I -> D -> J -> K -> E -> B -> L -> F -> G -> C -> A

(1) 전위 순회

전위 순회는 루트 노드 -> 왼쪽 서브트리 전위 순회 -> 오른쪽 서브트리 전위 순회 순서를 가지고 있다. 위 그림을 기준으로 설명하면, 다음과 같다.

• A 방문 후 왼쪽 서브트리의 루트 노드인 B를 방문.
• B를 기준으로 왼쪽 서브트리의 루트 노드인 D 방문.
• D를 기준으로 왼쪽 서브 트리의 루트 노드인 H 방문.
• H 이하 노드가 없기 때문에 바로 상위 노드의 오른쪽 노드인 I 방문.
• I 이하 노드가 없기 때문에 순회하지 않은 E 노드를 방문
• E 노드에서 D와 동일하게 왼쪽(J) -> 오른쪽(K) 탐색.
• 더 이상 최상위 루트 노드 기준 왼쪽 노드가 없기 때문에 C 노드 방문.
• 앞의 순회와 동일하게 왼쪽을 최우선해서 F, I 탐색 후 G 노드 방문.
• 전위 순회 : A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> G

방문 과정은 굉장히 복잡해보이지만, 이걸 의사 코드로 구현하면 다음과 같다.

전위 순회(노드) : 
	if 노드가 존재하지 않으면:
    	return
    노드 값 출력
    전위 순회(노드의 왼쪽 자식)
    전위 순회(노드의 오른쪽 자식)

(2) 중위 순회

중위 순회는 전위 순회와 달리 왼쪽 서브트리 중위 순회 -> 루트 노드 -> 오른쪽 서브트리 중위 순회의 순서를 가지고 있다. 위 트리를 순회하는 과정을 보면 다음과 같다.

• 먼저 A의 왼쪽 서브트리 중 가장 왼쪽인 D가 루트 노드인 서브 노드를 방문한다.
• D를 기준으로 중위순회를 하므로, 위 중위 순회의 순서처럼 H -> D -> I 를 차례대로 방문한다.
• 이제 왼쪽 서브트리가 끝났으므로, B(루트)를 방문한 뒤, 오른쪽 서브트리에 방문한다.
• 오른쪽 서브트리(E)의 왼쪽부터 차례대로 J -> E -> K를 방문한다.
• 왼쪽 서브트리가 전체적으로 끝났으므로 이제 루트 노드인 A를 방문하고 오른쪽 서브트리를 중위 순회한다.
• 오른쪽 서브트리(C)의 왼쪽 서브트리를 중위 순회(I -> F) 후 루트 노드 방문(C) 후 마지막 오른쪽 노드(G)를 방문하면 끝난다.
• 중위 순회 : H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> C -> G

중위 순회의 의사코드는 다음과 같다.

중위 순회(노드):
	if 노드가 존재하지 않으면 :
    	return
    중위 순회(노드의 왼쪽 자식)
    노드 값 출력
    중위 순회(노드의 오른쪽 자식)

(3) 후위 순회

마지막으로 후위 순회에 대해 알아보자. 후위 순회는 왼쪽 서브트리 후위 순회 -> 오른쪽 서브트리 후위 순회 -> 루트 노드의 방문 순서를 지니고 있다. 이 같은 순서를 기억하고 위 트리를 기준으로 설명하면 다음과 같다.

• 가장 왼쪽 서브트리인 D를 기준으로 후위순회 하므로 H를 방문한 다음, 오른쪽 I를 방문하고 루트 노드인 D를 방문한다.
• 그다음 루트 노드인 B를 기준으로 왼쪽이 끝났으니 오른쪽 서브트리를 후위 순회한다.
• 오른쪽 서브트리에서 차례대로 왼쪽, 오른쪽, 루트를 방문한다.(J -> K -> E)
• B의 자식 노드를 모두 탐색했으므로 마지막 루트 노드인 B를 방문한다.
• 이제 A를 기준으로 오른쪽 서브트리에서 앞의 과정을 반복해서 차례대로 방문한다.(L -> F -> G -> C)
• 모두 방문했으면 마지막으로 A를 방문한다.
• 후위 순회 : H -> I -> D -> J -> K -> E -> B -> L -> F -> G -> C -> A

후위 순회의 의사 코드는 다음과 같다.

후위 순회(노드):
	if 노드가 존재하지 않으면:
    	return
    후위 순회(노드의 왼쪽 자식)
    후위 순회(노드의 오른쪽 자식)
    노드 값 출력

 

위 3가지 순회에 대해 간단히 정리하면 다음과 같다.

• 전위 순회 : 루트 노드 -> 왼쪽 서브트리 전위 순회 -> 오른쪽 서브트리 전위 순회
• 중위 순회 : 왼쪽 서브트리 중위 순회 -> 루트 노드 -> 오른쪽 서브트리 중위 순회
• 후위 순회 : 왼쪽 서브트리 후위 순회 -> 오른쪽 서브트리 후위 순회 -> 루트 노드

1-3 트리의 종류

트리에는 순회 방법뿐만 아니라 상황에 따라 다양한 트리가 사용될 수 있다. 트리의 종류는 꽤 다양하며 대표적인 것들에 대해서만 차례대로 알아보자.

(1) 이진 트리

자식 노드의 개수가 2개 이하인 트리를 말한다. 트리라고 말하면 떠올리는 대표적인 형태의 트리로 이진트리의 형태에 따라 조금씩 다르게 부르기도 한다.

• 편향된 이진트리 : 자식 노드가 한 쪽으로만 치우치게 생성된 이진 트리
• 정 이진 트리 : 자식 노드의 개수가 0, 혹은 2개인 경우
• 포화 이진 트리 : 리프 노드를 제외한 모든 노드가 자식을 2개씩 가지고 있고, 모든 리프 노드의 레벨이 동일한 경우
• 완전 이진트리(complete binary tree) : 리프 노드를 제외한 모든 노드가 자식을 2개씩 가지고 있고, 리프 노드가 왼쪽부터 순서대로 존재하는 경우
• 이진 탐색 트리(BST) : 탐색에 활용되는 이진트리로 특정 노드를 기준으로 왼쪽은 모두 값이 작고, 오른쪽은 그 노드보다 큰 값을 지닌 형태의 이진 트리
  • O(log n)으로 원하는 값을 탐색할 수 있는 장점이 있음.
  • 다만 단점으로 편향된 이진 탐색 트리라면 O(n)의 시간이 걸림.(최악)
• 힙(heap) : BST와 유사하게 탐색에 특화된 완전 이진 트리로 2가지 종류가 있다.
  • 최소 힙 : 부모 노드가 자식 노드의 값보다 작은 값으로 이루어짐
  • 최대 힙 : 부모 노드가 자식 노드의 값보다 큰 값으로 이루어짐.
• 자가 균형 이진 탐색 트리 : 이진 탐색 트리의 단점을 해결해 왼쪽과 오른쪽 서브 트리의 균형을 맞추는 트리로 크게 AVL 트리와 RB 트리가 존재한다.
  • RB 트리 : 노드에 색을 칠하는 규칙과 칠해진 색(블랙, 레드)을 기준으로 균형을 맞춘다.
    • 루트, 리프 노드는 블랙이다.
    • 레드 노드의 자식 노드는 블랙 노드.
    • 루트 노드에서 임의의 리프 노드에 이르는 경로의 블랙 노드 수는 같다.
  • AVL 트리 : RB 트리보다 조금 더 엄격한 규칙으로 좌우 자식 간의 높이 차이를 기준으로 균형을 맞춘다.
• B 트리 : RB 트리와 유사하게 균형을 유지하는 트리이지만, 다진 탐색 트리의 한 종류이다. 다진 탐색 트리는 여러 자식 노드를 가질 수 있는 트리를 의미한다. B 트리는 실무에서 파일 시스템이나 DB에서 자주 사용된다.(현재는 B+ 트리도 많이 사용한다.)
  • 한 노드가 가질 수 있는 최대 자식 노드의 개수가 M개인 B 트리를 M차 B트리라고 한다.
  • M차 B트리의 최소 자식 노드의 개수는 (루트, 리프 제외)[M / 2] 개다.

---

사실 트리의 종류는 더 많고 다양하며, 트리의 순회 방식에 대해서도 저 방식 이외에 방법도 존재한다. 추후에 찾아보는 것을 권장하며 마지막으로 관련된 추천 용어 정도만 남기겠다.

• 레벨 순서 순회
• AVL, RB, B, B+ 트리
• 세그먼트 트리
• 펜윅 트리
• 트라이

---

참고

[자료구조] 이진 트리 & 이진 탐색 트리 (BST: Binary Search Tree) - 하나몬

 

[자료구조] Red-Black tree / AVL tree