트리

 트리를 본격적으로 살펴보기에, 앞서 트리 각 부분에 대한 명칭을 살펴보자.

 

 그래프 vs 트리

 그래프와 트리의 차이점은 트리는 순환 구조를 갖지 않는 그래프임 이다. 트리는 크게 그래프의 범주에 포함되지만 그래프와 달리 트리는 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다.

 

 

이진 트리

 트리중에서 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree,BST)이다. 각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 다진 트리)라고 한다. m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리(Binary Tree)라고 구분해서 부른다. 이진 트리는 왼쪽, 오른쪽. 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결할 뿐만 아니라 여러 가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니고서는 대부분 이진트리를 일컫는다.