그래프, 그 두 번째 이야기 | 트리 (1)

트리란 cycle이 없는 연결 무향 그래프를 뜻한다.

즉, 쉽게 말해서 어떤 정점에서 출발해도 같은 간선을 지나지 않고 다시 자기 자신으로 돌아올 수 있는 길이 존재하지 않으며, 어떤 두 정점을 선택해도 간선을 통해 한 정점에서 다른 정점으로 이동할 수 있는 그래프이다.

트리는 다음과 동치임이 알려져 있다. 즉, 트리는 아래 조건들을 만족하며, 아래 조건 중 하나라도 만족하면 트리이다.

 

1. 임의의 두 정점을 잡았을 때, 두 정점을 잇는 경로는 반드시 딱 하나 존재한다.

2. 연결 그래프이며, 어떤 간선을 제거해도 연결 그래프가 아니게 된다

3. cycle이 없으며, 서로를 잇는 간선이 없는 어떤 두 정점 사이에 간선을 만들어도 cycle이 생긴다.

하지만 정보에서는 주로 정점 간의 관계를 부모-자식 관계로 설명하며, 부모가 존재하지 않는 루트 노드를 설정한다. 서로간에 간선이 있는 두 정점에서 루트에 더 가까운 정점이 부모가 된다. 그리고 부모의 부모의 부모의...부모인 경우 조상이라고 부르며, 자식의 자식의 자식의..자식인 경우 자손이라고 부른다. 이렇게 했을 때 얻을 수 있는 이득이 참 많다.

트리가 쓰이는 자료구조는 정말 많다. 대충 정리하자면

힙(heap)

세그먼트 트리(segment tree)

이진 탐색 트리(binary search tree)

트라이

dfs 트리

리 차오 트리

등등등... 이 있을 수 있다.

앞으로 이 자료구조들을 하나씩 하나씩 포스팅해 볼 예정이다.