트리의 기초

트리(tree)는 그래프의 일종이다.

그래프란 정점(vertex)들이 간선(edge)들로 연결되어있는 구조를 뜻한다.
정점은 node, 노드라고도 부른다.

지하철 노선도에서 각 역이 정점, 이웃한 역을 잇는 노선이 간선이 될 수 있다.
도로와 도로가 만나는 교차로들을 정점, 교차로 사이의 도로를 간선이라고도 말할 수 있다.

그럼 트리는 뭘까? 어떤 조건을 만족하는 그래프를 트리라고 부른다.
이 조건을 더 쉽게 이해하려면... 일단 그림을 보자.

나무에서 가지가 뻗어나가는 모양을 상상하자. 이 그래프는 정점이 6개, 간선이 5개이다. 그리고 이 그래프는 트리이다.

트리의 조건은 다음 중 한 가지만 만족하면 트리이다. 왜냐하면 모두 서로 동치인 조건이기 때문이다.

1. 간선의 갯수가 정점의 갯수보다 하나 적으며(E=V-1), 모든 정점이 서로 연결되어 있다. 여기서 연결되어 있다는 것은, 모든 정점끼리 각각 오가는 경로가 하나 이상 존재한다는 것이다.

2. 간선의 갯수가 정점의 갯수보다 하나 적으며(E=V-1), 사이클이 없다. 여기서 사이클은 간선을 하나 이상 지나서 자기 자신으로 돌아오는 경로를 말한다.

3. 모든 정점이 서로 연결되어 있으며, 사이클이 없다.

4. 임의의 두 정점을 골랐을 때, 그들 사이를 오가는 경로가 반드시 유일하게 존재한다.

즉 위의 네 개의 조건 중 어느 하나를 만족하면, 나머지 세 개도 만족함을 보일 수 있다.

트리에는 루트(root)라고 부르는 특수한 정점이 있을 수도 있고, 없을 수도 있다.
특수한 정점이라고 해서 정점이 하나 더 있는 것은 아니고, 트리의 정점들 중에 어떤 것은 루트일 수 있다는 것이다. 있다면 하나만 루트여야 한다.

루트가 있는 트리는 '부모(parent)'라는 관계가 존재한다.
두 정점 A, B가 간선으로 연결되어 있다면, A가 B의 부모이거나, B가 A의 부모이다.
루트를 제외한 모든 정점은 부모 정점이 한 개씩 있다.
부모의 부모의 부모의 .. 이렇게 부모를 타고 쭉 올라가다 보면 반드시 루트가 나온다.

이것을 어떻게 생각하면 좋은가 하면, 루트의 정점을 손으로 집어들고, 나머지 정점이 축 처지는 모양을 생각하면 된다.
정점마다 자기가 매달리고 있는 정점이 하나 있을 것이고, 그것이 그 정점의 부모이다.

부모, 부모의 부모, 부모의 부모의 부모, ... 이렇게 자신과 루트를 잇는 경로 상의 모든 정점을 그 정점의 조상(ancestor)이라고 칭한다.
보통은 자기 자신도 포함한다.

두 노드의 최저 공통 조상(lowest common ancestor, LCA)을 말하는 것은, 두 노드의 공통 조상 중 높이가 가장 큰 것을 의미한다.
매우 직관적인 그림 하나로 설명을 대신한다.

별로 직관적이지 못한 것 같다.

트리 문제를 처음 접하는 사람들에게는 그래프가 익숙하지 않거나, 어떻게 풀면 좋을지 감이 안 잡힐 수 있는데,
트리의 모양이나 여러 개념들을 이 글을 통해서 이해할 수 있게 되면 좋겠다.