[자료구조/Data structure]Binary Tree, 이진 트리

트리에 관하여

안녕하세요. Air8입니다. 오늘의 얘기는 Tree에 관하여입니다.

저는 회사에 맨 처음 입사해서 알고리즘을 짤 때 트리를 개념적으로만 알고 있었습니다. 뭐 대충 중심에서 뻗어져나가는 뭐 그런거겠지. 이런 생각을 가지고 있었는데, 어떻게 구현하는 지는 그저 구름 속에서 휘젓고 있었죠. 너무나 간단한 단어 때문에 누구한테 물어볼 필요도 없는 그런 것이 저한테는 트리였습니다.

 

 자료구조 측면에서 본다면 트리는 조금 복잡합니다. 나름 규칙도 있구요. Hierarchical structure(계층 구조)로 표현하는 Abstract Data Type(추상 데이터 형식)인 트리를 알아보겠습니다. 여기서는 Preorder traversal, Inorder traversal, Postorder traversal이 언급되나 설명이 없으니 아래를 먼저 참고해주세요. 또한, 연결리스트 및 리스트를 언급합니다만 리스트에 대한 설명은 추후에 업데이트하겠습니다.

 

순회 : https://tinyworldwithair.tistory.com/34

 

먼저 트리 내부에서 사용하는 용어를 설명합니다.

 

노드(node)	트리의 원소
엣지(edge)	노드와 노드의 연결선
루트(root)	부모가 없는 노드 ( 최상위 노드 )
서브트리(subtree)	한 개의 노드와 그 노드의 자식을 포함
단말노드(terminal, leaf)	자식이 없는 노드 ( 최하단 노드 )
비단말노드(non-terminal, internal)	자식이 있는 노드 ( 중단 노드 )

트리 외부에서 사용하는 용어를 설명합니다.

 

부모 노드(parent node)	자신의 노드의 바로 상위노드
자식 노드(child node)	자신 바로 아래의 노드
형제 노드(sibling node)	동일 레벨을 가졌으며 같은 부모를 가진 노드
노드의 차수(degree)	자식 노드의 개수
트리의 차수(order)	모든 노드 degree의 최대값
레벨(level)	각 층의 번호(Root의 level은 1이다)
높이(height)	트리의 최대 레벨

트리는 배열과 리스트로 구성할 수 있습니다. 그러나 여기서는 리스트로 설명하겠습니다.

[1] 이진 트리(Binary tree)

특징 :

노드가 n개면 엣지는 n - 1

높이가 h면 노드는 h개 ~ 2^h - 1개 

노드의 개수만 알고 있어도 높이의 범위를 구할 수 있습니다. 예를 들어 노드가 100개라면 2^6 = 64고 2^7 = 128이니 높이는 7에서 100까지라고 볼 수 있습니다.

노드와 높이의 관계

 

종류 :

포화 이진 트리(full binary tree)

완전 이진 트리(complete binary tree)

포화/완전 이진트리만 알면 됩니다. 이미지 참고 : https://ehclub.co.kr/2951

이진 트리의 탐색법 :

깊이 우선 탐색(DFS, Depth-First Search) : 전위순회, 중위순회, 후위순회

너비 우선 탐색(BFS, Breadth-First Search) : 레벨순회

참고 - 이진 트리 순회의 Big-O notation(정렬되지않은 탐색이다 보니 풀지 않아도 결국 O(n)이 나올 수 밖에 없다)