코드 스테이츠 - 자료 구조 2(Tree/BST/Graph)

Tree

Tree란?

자료 구조에서 Tree는 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다.

그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.

Tree

가계도와 흡사해 보이는 이 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.

 

 

Tree의 구조와 특징

트리 구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결한다.

각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.

Tree 구조

위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

 

자료 구조 Tree는 깊이와 높이, 레벨등을 측정할 수 있다.

 

깊이 (depth)

 

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0이다. 위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1이라고 표현한다. D, E, F, G의 깊이는 2다.

 

레벨(Level)

 

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다. depth가 0인 루트 A의 level은 1이다. depth가 1인 B와 C의 level은 2다. D, E, F, G의 레벨은 3이다. 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.

 

높이(Height)

 

트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.

트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다. 위 그림에서 H, I, E, F,G의 높이는 0이된다.

D의 높이는 1이다. B의 높이는 2다. 이때 B는 D의 height + 1을 가진다.  따라서, 루트 A의 높이는 3이다.

 

서브 트리(Sub tree)

 

트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다.

(D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G)도 서브 트리다.

 

 

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

Tree의 장점

 

1. 효과적인 계층 구조 표현

 

Tree 자료 구조는 계층 구조를 나타내는 데에 효과적이다.

예를 들어, 회사에서 조직도를 작성할 때 Tree 자료 구조를 활용하여 부서와 직원들 간의 계층 구조를 표현할 수 있다.

 

2. 정렬과 탐색에 활용

 

 

Tree 자료 구조는 이진 탐색 트리, 힙(Heap) 등과 같은 다양한 형태로 사용될 수 있으며, 정렬과 탐색을 위한 알고리즘을 구현하는 데에도 사용된다.

 

3. 삽입과 삭제가 쉬움

 

 

Tree 자료 구조는 노드의 삽입과 삭제가 쉽다. 삽입 및 삭제 시에 해당 노드의 부모와 자식 노드만 수정하면 되기 때문이다.

 

4.구조 파악이 용이

 

 

Tree 자료 구조는 시각화가 쉬우므로, 트리를 시각적으로 표현하여 이해하기 쉽다.

 

5.다양한 분야에서 활용

 

 

Tree 자료 구조는 데이터베이스, 알고리즘 등 다양한 분야에서 활용된다. Tree 자료 구조가 다양한 문제를 해결하기 위한 다양한 알고리즘의 기초가 되기 때문이다.

 

 

 

BST (Binary Search Tree)

이진 트리(Binary Tree)란?

자식 노드가 최대 두 개인 노드들로 구성된 트리다. 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눈다.

이진 트리는 자료의삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

 

이진 탐색이란?

이진 탐색 알고리즘이란 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나이다.

이진 탐색 알고리즘은 오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘이다.

1. 전체 데이터에서 중간(Root)에서 내가 찾고자 하는 값이 있는지 확인한다.
2. 중간값이 내가 찾고자 하는 값이 아닐 경우, 오름차순으로 정렬된 데이터에서 중간값보다 큰 값인지 작은 값인지 판단한다.
3. 찾고자 하는 값이 중간값보다 작은 값일 경우, 데이터의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 탐색을 반복 수행한다.
4. 찾고자 하는 값이 중간값보다 큰 값일 경우, 데이터의 중간값의 다음 값부터 맨 마지막까지를 탐색 범위로 잡고 탐색을 반복 수행한다.

 

이진 탐색 트리(Binary Search Tree)란?

이진 탐색의 속성이 이진 트리에 적용된 특별한 형태의 이진 트리이다.

 

이진 탐색 트리는 이진 탐색의 알고리즘이 이진 트리에 적용된 형태로 트리의 루트 노드는 이진 탐색에서 전체 데이터의 중간값이 된다.

루트노드의 왼편 서브 트리의 값들은 이진 탐색 알고리즘에 기반하여 모두 루트노드의 값보다 작은 값들이 자리 잡고 있고 루트노드의 오른편 서브 트리의 값들은 루트노드의 값보다 큰 값들이 자리 잡고 있어야 한다.

 

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다. 

이진 탐색 트리

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다.

균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제다. 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있습니다.

 

 

이진 탐색 트리 탐색 과정

 

이진 탐색 트리의 탐색은 다음과 같은 과정을 거친다.

 

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 만약 찾고자 하는 값이라면 탐색을 종료한다.

2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.

3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.

 

이 과정을 찾고자 하는 값을 찾을 때까지 반복해 진행한다. 만약 값을 찾지 못한다면 그대로 연산을 종료하게 된다.

이러한 탐색 과정을 거치면 최대 트리의 높이만큼 탐색을 진행한다.

5값을 찾는 이진 탐색 트리

위와 같은 이진 탐색 트리에서 5라는 값을 찾으려고 한다면 과정은 아래와 같이 진행된다.

제일 처음 찾고자 하는 값과 루트 노드를 비교한다.

 

1. 루트 노드 = 10 이므로 루트 노드보다 찾고자 하는 값이 작기 때문에, 왼쪽 서브트리로 탐색을 진행한다.

2. 이후 마주친 노드는 7이다. 찾고자 하는 값은 5이기 때문에 다시 7을 기준으로 왼쪽 서브 트리로 탐색을 진행한다.

3. 이후 만난 값이 찾고자 하는 값이기 때문에 탐색이 종료된다.

 

10부터 5까지 3번의 탐색을 진행했다. 만약 찾는 값이 3이었다면 4번의 연산이 진행되었을 것이다.

즉, 트리 안의 값을 찾는다면 무조건 트리의 높이(h) 이하의 탐색이 이루어 진다.

 

하나 알아둬야 할 점은, 트리 안에 찾고자 하는 값이 없더라도 최대 h번(트리의 높이)만큼의 연산 및 탐색이 진행 된다는 것이다. 만약 13을 찾는다는 가정하에 마지막 노드 값은 14이고, 13은 14 보다 작기 때문에 왼쪽 서브 트리로 탐색을 진행해야 한다. 하지만 오른쪽 서브트리가 없으므로 14에서 탐색이 종료된다. 이렇게 트리안에 찾고자 하는 값이 없더라도 최대 h번의 연산 및 탐색이 진행되게 된다.

 

 

이진 탐색 트리에서 노드 추가

 

이진 탐색 트리에서 노드를 추가할 때는 노드의 값이 현재 노드보다 작으면 왼쪽 서브 트리에, 크면 오른쪽 서브 트리에 추가한다. 이 작업은 노드를 삽입하려는 위치까지 재귀적으로 탐색하며 이루어진다. 삽입된 노드를 기준으로 다시 한번 왼쪽과 오른쪽 서브 트리가 이진 탐색 트리의 특성을 만족하는지 확인하면서 트리의 구조를 유지한다.

2라는 값을 추가하는 이진 탐색 트리

위와 같은 이진 탐색 트리에서 2라는 값을 추가하려고 한다면 과정은 아래와 같이 진행된다.

제일 처음 추가 하고자 하는 값과 루트 노드를 비교한다.

 

1. 루트 노드 = 10 이므로 루트 노드보다 작기 때문에, 왼쪽 서브 트리로 삽입을 위한 비교를 시작한다.

2. 이후 마주친 노드는 5다. 넣고자 하는 값은 2이므로 다시 5를 기준으로 왼쪽 서브 트리로 삽입을 위한 비교를 시작한다.

3. 이후 마주친 노드는 3이다. 넣고자 하는 값은 2이므로 다시 3을 기준으로 왼쪽 서브 트리로 삽입을 위한 비교를 시작한다.

4. 3을 기준으로 하위 노드가 존재하지 않으므로, 3의 좌측 노드에 2를 추가한다.

 

 

이진 탐색 트리에서 노드의 삭제

 

이진 탐색 트리에서 노드를 삭제할 때는 여러 경우를 고려해야 한다.

 

1. 삭제할 노드가 리프 노드인 경우

리프 노드는 자식 노드가 없기 때문에 그냥 삭제가 가능하다.

 

2. 삭제할 노드의 자식 노드가 하나인 경우

삭제할 노드의 자식 노드가 하나인 경우, 삭제할 노드의 부모 노드와 삭제할 노드의 자식 노드를 연결해 주면된다.

아래 그림처럼 3을 키로 가지는 노드를 제거하고, 기존의 2라는 키를 가진 노드의 위치를 삭제된 데이터 위치로 이동한다.

삭제할 노드의 자식 노드가 한 개인 경우

 

3. 삭제할 노드의 자식 노드가 두 개인 경우

삭제할 노드를 대체할 노드를 찾아야 한다. 이진 탐색 트리에서 대체할 노드는 삭제할 노드의 오른쪽 서브 트리 중 가장 작은 값의 노드 혹은 삭제할 노드의 왼쪽 서브 트리 중 가장 큰 값의 노드여야 한다. 대체할 노드를 찾은 후, 삭제할 노드와 대체할 노드를 서로 교환한다. 그런 다음 대체할 노드를 삭제한다.

이 작업을  재귀적으로 수행 하면서 트리의 구조를 유지한다.

 

아래 그림은 5를 제거하기 위해서 진행되는 과정이다.

 

1. 5를 가지고 있는 노드를 대체할 노드를 찾아야 한다.

2. 왼쪽 자식 노드에서 가장 큰 값을 가진 노드는 3, 우측 자식에서 가장 작은 값을 가진 노드는 6이다.

3. 좌측 3과 5의 위치를 변경한다.

4. 5를 삭제한다. 5를 지우는 과정에서 5의 자식 노드 유무에 따라 자식 노드가 없는 경우, 자식 노드가 하나인 경우, 자식 노드가 두 개인 경우로 나눠 다시 삭제 작업을 재귀적으로 실행한다.

삭제할 노드의 자식 노드가 두 개인 경우

 

 

Graph

그래프(Graph)란?

그래프(Graph)는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조이다.

자료 구조의 그래프는 마치 거미줄 처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습이다.

자료구조 Graph 예시

 

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.

 

Graph의 표현 방식

 

인접 행렬

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접한다고 이야기한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표다.

만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다. 

위 그래프를 인접 행렬로 표시하면, 다음과 같은 2차원 배열로 나타낼 수 있다.

int[][] matrix = new int[][]{
	{0, 0, 1}, // A정점에서 이동 가능한 정점을 나타내는 행
	{1, 0, 1}, // B정점에서 이동 가능한 정점을 나타내는 행
	{1, 0, 0}. // C정점에서 이동 가능한 정점을 나타내는 행
};

• A의 진출차수는 1개: A —> C
  • [0][2] == 1
• B의 진출차수는 2개: B —> A, B —> C
  • [1][0] == 1
  • [1][2] == 1
• C의 진출차수는 1개: C —> A
  • [2][0] == 1

 

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.

각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

위 그래프를 인접 리스트로 표시하면, 다음과 같은 인접 리스트로 나타낼 수 있다.

// A, B, C는 각각의 인덱스로 표기한다. 0 == A, 1 == B, 2 == C
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    graph.add(new ArrayList<>(Arrays.asList(2, null)));
    graph.add(new ArrayList<>(Arrays.asList(0, 2, null)));
    graph.add(new ArrayList<>(Arrays.asList(0, null)));

graph.get(0) == [2, null] == 0 -> 2 -> null
graph.get(1) == [0, 2, null] == 1 -> 0 -> 2 -> null
graph.get(2) == [0, null] == 2 -> 0 -> null

B는 A와 C로 이어지는 간선이 두 개가 있는데, A가 C보다 먼저다. 순서는 중요하지않을까?

 

보통은 중요하지 않다. 그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선순위를 고려해 구현할 수 있다. 이때, 리스트에 담긴 정점들을 우선순위별로 정렬할 수 있다. 우선순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.

 

우선순위를 다뤄야 한다면 더 적합한 자료 구조(ex. queue, heap)를 사용하는 것이 합리적이다. 따라서 보통은 중요하지 않다. (언제나 예외는 있지만)

 

인접 리스트는 언제 사용할까?

메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.

인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.

 

Graph 용어 정리

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소다.
• 간선 (edge): 정점 간의 관계를 나타낸다. (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.
• 가중치 그래프 (weighted Graph): 연결의 강도가 얼마나 되는지 적혀 있는 그래프를 뜻한다.
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀 있지 않는 그래프를 뜻한다.
• 무향(무방향) 그래프 (undirected graph): 간선에 방향성이 존재하지 않는다.
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.