19-5.트리

19-5-가.트리의 용어

여기까지 알아본 배열이나 연결 리스트, 스택, 큐 등은 모두 1차원의 선형적인 구조를 가지는데 비해 트리는 2차원적인 구조를 가진다. 구조가 입체적이고 다소 복잡하기 때문에 배열이나 연결 리스트보다는 다루기 어렵고 까다롭다. 또한 스택이나 연결 리스트처럼 구현 방법이 정형화되어 있지 않고 적용하는 알고리즘에 따라 천차 만별로 모양이 달라져 응용력을 필요로 하기도 한다.

그러나 입체적인 구조로 인해 자료의 삽입, 삭제 속도가 빠르면서도 검색 속도까지 만족할만하며 용량이 커지더라도 속도의 감소가 적어 대용량의 자료를 다룰 때 훨씬 더 효율적이다. 어느 정도 규모가 있고 복잡한 데이터를 다룰 때는 주로 트리가 사용되는데 상용 DB 엔진들도 트리 구조로 데이터를 관리한다. 디렉토리 구조나 기구도, 토너먼저 대진표 등과 같이 계층적인 자료들을 다룰 때도 트리가 가장 어울린다.

트리를 프로그래밍하는 방법을 배우기 전에 우선 트리에서 사용하는 용어부터 정리해 보자. 트리는 말뜻 그대로 나무를 뜻하므로 트리 구조에서 사용하는 용어들은 나무의 각 부분들인 경우가 많고 노드끼리 계층적인 관계를 이루므로 족보의 용어가 사용되기도 한다. 용어 자체는 상식적이므로 쉽게 이해되지만 같은 대상을 칭하는 동의어가 많아 조금 헷갈린다. 다음은 트리의 한 예인데 이 예를 통해 트리의 용어를 정리해 보자.

진짜 나무들은 뿌리가 밑에 있고 가지와 잎이 위로 자라지만 트리를 그릴 때는 위 그림처럼 루트를 위쪽에 그리는 것이 보통이다. 트리는 실제 데이터를 가지는 노드(Node)와 노드를 연결하는 링크(Link)로 구성된다. 위 그림에서 원으로 표현된 것이 노드이며 원을 잇는 선분들이 링크인데 노드, 링크라는 용어 대신 버텍스(Vertex), 에지(Edge)라는 용어를 사용하기도 한다. 트리의 노드들은 항상 루트로 향하는 링크를 하나씩 가지되 루트는 링크를 가지지 않으므로 링크의 개수는 항상 노드보다 하나 더 작다. 위의 트리는 노드가 14개이고 링크는 13개이다.

노드 중에 가장 기본이 되는 최상위 노드를 루트(Root)라고 부른다. 모든 트리는 단 하나의 유일한 루트를 가지며 루트 아래로 무수히 많은 노드들이 있다. 트리를 구성하는 노드끼리의 관계는 흔히 가족 관계에 비유하는데 아래쪽의 노드를 자식이라고 하며 위쪽의 노드를 부모라고 한다. 위 그림에서 B와 C는 A의 자식이며 E와 F의 부모는 B이다. 같은 부모를 가진 노드들을 형제라고 하는데 G, H는 공동의 부모 C에 소속되어 있으므로 형제 관계이다. 직속 관계가 아니더라도 아래쪽에 있으면 후손이며 위쪽에 있으면 선조라고 한다.

레벨(Level)은 루트에서의 거리를 의미하는데 루트의 레벨은 1이다. C 언어는 모든 숫자를 0부터 시작하지만 트리의 레벨은 1부터 시작(One Base)한다. 위의 트리에서 B의 레벨은 2이고 E의 레벨은 3이고 M의 레벨은 4이다. 높이(Height, 또는 깊이라고도 한다.)는 트리의 최대 레벨인데 가장 아래쪽에 있는 N의 레벨이 5이므로 이 트리의 높이는 5가 된다.

경로(Path)란 특정 노드에서 다른 노드로 가는 길이다. 어떤 노드에서 다른 노드로 가려면 공동의 조상까지 올라간 후 다시 아래로 내려 가야 하므로 두 노드 사이의 경로는 단 하나만 존재하는 특성이 있다. K에서 G로 가는 경로는 K-E-B-A-C-G 단 하나밖에 없다. 이에 비해 경로가 여럿 존재하는 자료 구조가 있는데 이를 그래프(Graph)라고 한다.

차수(Degree)는 자식 노드의 개수인데 B의 차수는 3, C의 차수는 2, M의 차수는 0이다. 차수가 0인 노드, 그러니까 자식이 하나도 없는 노드를 잎(Leaf) 노드 또는 외부(External) 노드라고 하며 자식이 있는 노드를 내부(Internal) 노드라고 한다. 위 트리에서 F, H, I, J, K, M, N이 트리의 마지막에 달린 잎 노드들이며 나머지는 내부 노드들이다.

노드의 자식들 사이에 순서가 있는 노드를 순서 트리(Ordered Tree)라고 하며 순서가 의미없는 노드를 비순서 트리(Oriented Tree)라고 한다. 다음 두 트리를 보자.

둘 다 A 밑에 B와 C가 있는데 순서 트리라면 이 둘은 다른 것이고 비순서 트리라면 같은 것이다. 순서 트리는 자식의 존재뿐만 아니라 순서도 의미가 있는 것이고 비순서 트리는 순서에 상관없이 어떤 자식이 있는가만이 중요한 트리이다.

트리를 구성하는 작은 트리를 서브 트리(Sub Tree)라고 한다. 마치 디렉토리의 계층에서 디렉토리 밑에 서브 디렉토리가 있는 것처럼 트리 아래에도 똑같은 모양의 서브 트리가 존재한다. 위 그림의 A 트리는 B 서브 트리와 C 서브 트리로 구성되어 있고 C 서브 트리는 다시 G, H 서브 트리로 구성되어 있다. 트리 여러 개가 모인 것은 포리스트(Forest)라고 하는데 나무들이 모여 숲을 이루는 것과 같다.