트리 (Trees)

트리(tree)는 데이터의 검색과 탐색에 아주 널리 이용되는 자료구조로서 데이터베이스 시스템 또는 검색 엔진 등에서 아주 많이 이용된다. 트리는 순환하는 길이 없는 그래프(graph)이고, 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.

 

 

 

트리의 용어 이해

 

 

 

 

이진 트리 (binary trees)

모든 노드의 차수가 2 이하인 트리를 말한다. 이진트리는 재귀적으로 정의할 수 있는데 빈트리(empty tree)이거나 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리)이면 이진트리이다.

 

 

 

포화 이진 트리 (full binary tree)

모든 레벨에서의 노드들이 모두 채워져 있는 이진트리를 말한다. 포화 이진 트리는 높이가 K이고 노드의 개수가 2^K -1개인 이진트리라는 속성을 가진다. 

 

 

 

완전 이진 트리 (complete binary tree)

높이 k인 완전 이진트리는 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진트리로 구성이 되어있고 단, 마지막 레벨 k-1에 풀로 채워져 있지 않더라도 왼쪽부터 노드가 순차적으로 채워져 있다면 완전 이진트리라고 한다.