[Algorithm] Tree와 Graph | 이진 트리와 이진 탐색 트리(BST: Binary Search Tree)

Tree

단방향 그래프로, 계층형 비선형(하나의 데이터 뒤에 여러 데이터가 연결) 구조이다. 루트(Root)를 시작으로 데이터인 노드(Node)들을 서로 간선(edge)으로 연결되어 있으며 무방향이다. 상하 계층 구조로, 부모 노드와 자식 노드가 있다.

 

Graph

여러 개의 점들이 거미줄처럼 서로 복잡하게 연결되어 있는 관계이다. 하나의 점을 정점(vertex)이라고 하고, 하나의 선을 간선(edge)이라고 한다.

 

🍇 인접 행렬

서로 다른 정점들이 인접한 상태인지를 표시한 행렬로, 2차원 배열의 형태로 나타낸다.

graph = [
    [0, 1, 1, 1],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]

0번째 노드와 1번째 노드가 연결되어 있다면 0행 1행에 1을 입력한다. 이어져 있다면 1(true), 이어져 있지 않다면 0(false)이다. 무방향 그래프일 경우 대각선 대칭이다. 가중치(연결의 강도가 얼마나 되는가) 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다.

특정 두 정점 사이의 연결 정보를 확인할 때 용이하며, 시간 복잡도가 O(1)이다. 가장 빠른 경로(shortest path)를 찾을 때 주로 사용한다. 특정 노드에 연결된 모든 노드를 검색할 때에는 시간 복잡도가 O(N)이다. 전체 노드를 탐색하면 O(N²)이 된다.

 

🍇 인접 리스트

arr = [[] for _ in range(3)]

arr[1].append(2)
arr[1].append(3)

각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담는다. 가중치를 표현하기 위해서는 연결 정보에 튜플 형태 등으로 추가적인 입력이 필요하다

실제 연결된 노드만 저장한다. 모든 연결 정보를 가져올 때의 시간 복잡도가 낮지만 상대적으로 메모리를 많이 차지한다. 노드가 서로 연결되어 있는지 확인하기 위해서는 arr[N]의 원소를 살펴야 한기 때문에 시간 복잡도는 O(N)이다.

🍓 가중치 그래프 vs. 비가중치 그래프

서로 관계가 있다는 사실 외에 추가적인 정보(연결의 강도)를 알 수 있는가?

서울—140km—대전, 대전—200km—부산, 부산—325km—서울 //가중치
서울 - 부산 , 서울 - 대전 //비가중치

 

🍓 진입차수(in-degree) / 진출차수(out-degree)

 

🍓 자기 루프(self loop)

정점에서 지출하는 간선이 곧바로 자기 자신에게 진입하는 경우

 

🍓 사이클(cycle)

한 정점에서 출발하여 다시 해당 정점으로 돌아올 수 있을 때

 

---

 

트리 구조는 특징에 따라 여러 이름으로 불린다. 이진 트리와 이진 탐색 트리가 가장 많이 사용된다.

 

이진 트리

• 자식 노드가 최대 두 개인 노드들로 구성된 트리이다.
• 왼쪽 자식 노드 + 오른쪽 자식 노드

 

🌱 자료의 삽입, 삭제 방법에 따른 분류

• 정 이진 트리(Full binary tree): 각 노드가 0개 혹은 2개의 자식 노드를 가진다.
• 완전 이진 트리(Complet binary tree): 마지막 레벨의 오른쪽을 제외하고 모든 노드가 가득 채워져 있다.
• 포화 이진 트리(Perfect binary tree): 정 이진 트리 + 완전 이진 트리
  • 모든 리프 노드의 레벨이 같고, 모든 레벨이 가득 채워져 있다.

https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

 

이진 탐색 트리(Binary Search Tree)

• 왼쪽 자식의 값 < 루트, 부모의 값 < 오른쪽 자식의 값
• 균형이 잡히지 않은 트리는 탐색하는 데 시간이 시간이 더 소요된다
• 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

 

---

 

트리 순회(Tree traversal)

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것이다. 트리 구조에서 노드를 순차적으로 조회할 때는 항상 왼쪽 → 오른쪽이다

• 전위 순회(preorder traverse): 루트 → 왼 → 오
• 중위 순회(inorder traverse): 왼 → 루트 → 오
• 후위 순회(postorder traverse): 왼 → 오 → 루트

 

💁‍♀️ 이진 트리와 BST 이외의 트리

💁‍♀️ 균형 이진 탐색 트리란?