자료구조 - 트리

그래프에서 확장된 개념으로 순회가 없는 그래프를 트리라고 할 수 있다.

 

 

트리의 구성은 위와 같이 표현이 가능하며 그래프와 동일하게 노드와 간선으로 이루어져있다. 

최상단 노드는 루트 노드라고 부르며 최하단의 노드들은 리프 노드라고 부른다.

노드 간 부모, 자식, 형제 관계가 존재하며 부모의 자식 노드들의 갯수를 차수라고 한다.

루트에서 리프 노드까지 간선의 갯수를 높이, 가장 많은 자식 노드의 레벨을 너비라고 한다. 

 

 

트리는 그래프에 비해 종류가 상당히 다양하며 필자가 본 경험이 있는 트리 자료구조들은 다음과 같다.

 

이진트리

힙 트리

AVL 트리

Red Black 트리

B 트리

Trie

 

오늘은 트리 자료구조의 기초인 이진 트리가 무엇인지 그리고 트리 순회 방법에 대해 알아보려한다. 

 

 

이진 트리는 위와 같이 2개 이하의 자식 노드를 가진 부모 노드로 구성된 트리를 의미한다. 여기서 트리의 순회란 위에 언급한 3개의 순회를 말한다.

 

먼저 전위 순회로 위 이진 트리를 탐색하면 다음과 같다.

 

 

전위 순회로 탐색 시 부모 노드를 먼저 확인 후 부모 노드가 방문 처리 되면 좌측 자식 노드로 이동 가능한지 확인한다. 좌측 자식 노드가 탐색 가능할 경우 좌측 자식 노드로 이동하며 방문 처리를 하고 우측 자식 노드를 확인한다. 이후 가장 최근 자식 노드가 비어있던 부모 노드로 이동한 뒤 다시 좌측과 우측 자식 노드를 확인한다. 

 

 

다음으로 중위 순회로 이진 트리를 탐색하면 다음과 같다.

 

 

중위 순회로 탐색 시 좌측 자식 노드를 먼저 확인한다. 이후 더 이상 진행할 좌측 노드가 없을 경우 부모 노드로 돌아아고 이후 우측 자식 노드를 확인하며 순차적으로 위로 올라간다. 결과적으로 루트 노드 기준 좌측의 탐색이 끝나면 우측으로 넘어오게 되며 이후 우측에서도 동일한 방식으로 진행한다. 

 

마지막으로 후위 순회로 이진 트리를 탐색하면 다음과 같다. 

 

후위 순회로 탐색 시 좌측 자식 노드를 먼저 탐색 후 방문 처리를 한 뒤 부모 노드로 넘어와 우측 자식 노드를 확인한다. 이후 양쪽 자식 노드를 둘 다 확인한 부모 노드를 방문 처리 후 다시 상위 부모 노드로 넘어가 동일 탐색을 진행한다. 결과적으로 부모 노드의 아래 하위 트리들을 전부 탐색한 후 마지막으로 부모를 처리하는 방식으로 진행하게 된다.

 

이렇게 다른 트리의 기본이 되는 이진 트리의 구성과 순회 방법에 대해 알아보았다. 확장된 개념의 트리들은 대부분 기존 트리에 알고리즘을 접목시켜 특정 속성의 값을 빠르게 찾을 수 있게 해주는데 종종 PS 에서 나오므로 향후 더 자세히 알아보도록 하자.