6.20 Dev Feedback (자료구조 Graph, Tree, BST)

Graph

자료구조의 graph는 여러 개의 점과 선으로 이어져 있는 복잡한 망으로 구성되어 있다.

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 직접적인 관계인 경우 두 점 사이를 하나의 선이 이어준다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다. 그래프에서는 점을 정점(vertex)이라고 표현하고, 선은 간선(edge) 이라고 한다. 간선은 양방향으로 데이터가 전달될 수 있는 양방향 간선과 한 방향으로만 움직이는 단방향 간선이 있다.

 

그래프의 실사용 예제

일상생활에서 자료구조 그래프를 사용하여 우리가 구현할 수 있는 것들은 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등이다. 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있다.

 

세 가지 중에서 내비게이션 시스템이 어떤 방식으로 자료구조 그래프를 사용하는지 살펴보자.

 

만일 우리가 회사 차를 타고 출장을 가야하는데, 경로가 서울에서 대전을 들렸다 부산을 가야한다.

 

이걸 네비에이션의 입장에서 본다면 3개의 정점이 있는 것이다. (서울, 대전, 부산)

그리고 각각의 정점을 이어주는 간선도 존재한다. (서울 - 대전, 대전 - 부산, 부산 - 서울)

이렇게 간선으로 이어줄 수 있으면 관계가 있는 것이다.

만일 우리가 호주에 있는 퍼스를 등록을 한다면 어떻게 될까? 우리가 회사 차를 타고 퍼스에 갈 수 없기때문에

간선이 이어지지 않을 것이다. 이런 상황을 그래프에선 관계가 없다라고 표현한다.

 

간선을 살펴보면 서울, 대전, 부산이 서로 관계가 있다는 것은 알 수 있지만, 각 도시가 얼마나 떨어져 있는지는 알 수 없다.

간선은 특정 도시 두 개가 이어져 있다는 사실만 알려줄 뿐, 그 외의 정보는 포함하지 않고 있기 때문이다.

이렇게 추가적인 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 이런 그래프를 비가중치 그래프 라고 한다. 간단한 자바스크립트 객체를 이용하여 비유한다면 현재의 상황은 다음과 같다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

위 정보만으로는 서울에서 부산까지 갈 수 있다는 사실 외에 파악할 수 있는 정보가 없다.

만일 네비게이션이라고 한다면, 그냥 서울에서 대전, 그리고 대전에서 부산, 부산에서 서울 갈 수 있어!!! 라고만 해주는 꼴이다.

네비게이션이 제대로 작동하려면, 적어도 각 도시간의 거리가 얼마나 되는지는 표시해야 할 것이다.

즉 현재의 비가중치 그래프를 가중치 그래프로 바꾸고, 각 도시간의 거리를 표시해야 한다.

 

비가중치 그래프는 각 정점간의 연결 유무만을 판단하는 반면, 가중치 그래프는 더 자세한 정보를 담을 수 있다.

• 정점: 서울, 대전, 부산
• 간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

이렇게 간선에 연결정도(거리 등)를 표현한 그래프를 가중치 그래프라고 한다. 네비게이션은 간선에 거리를 표기한 가중치 그래프가 확장되어, 수백만개의 정점(주소)과 간선이 추가 되어야 비로소 네비게이션에서 쓰는 자료구조와 유사해 지게 된다.

 

알아둬야 할 그래프 용어들

• 무(방)향그래프(undirected graph): 앞서 보았던 네비게이션 예제는 무(방)향 그래프이다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능하다. 하지만 단방향(directed) 그래프로 구현 된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능하게 된다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다.
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다. 네비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프이다.

인접 행렬

인접(adjacency)

두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다고 한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장하게 된다. 위의 네비게이션 예제라면, 거리를 입력하는 방식으로 네비게이션 그래프를 인접 행렬로 표현하면 다음과 같다.

• 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

인접 행렬은 언제 사용할까?

• 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이gk다.
  • 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다. 위 그래프를 인접 리스트로 표현하면 다음 그림과 같이 표현할 수 있다.

[그림] 네비게이션 그래프의 인접 리스트 예시

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

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

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

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

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.

Tree

DOM구조와 비슷하게 Root에서부터 시작돼서, 각 요소들이 나무처럼 뻗어가는 구조

그래프의 여러구조 중, 무방향 그래프의 하나이다. (즉, 양방향으로 접근이 가능하다)

• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 -> 간선을 통해서 인접 데이터에 양방향으로 진입이 가능
• 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.

DOM 트리구조와 비슷하게 생각하면 이해가 쉬울 듯 하다.

트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가진다. 위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이고, 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 부른다.

용어정리

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

깊이 (depth)

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

 

**단지 개념적으로만 이해를 하려 했었는데, 최근 이 개념을 왜 알아야 하는지 공부해야한다는 것을 알게 됐다.

왜 트리구조에서 depth라는 개념에 대해 알아야 하는 것일까?

 

트리구조에서의 Depth는 시간 복잡도를 구하는데 있어서 꼭 필요한 요소이다.

 

쉬운 예시를 위해 Binary Search Tree(BST)를 예시로 들어보자면

BST에서의 시간 복잡도는 log(N)이 된다.

그 이유는 n개의 노드가 주어질 때, 매 Depth마다 2개의 노드씩으로 분할되기 때문에 2^depth = N이 되고

따라서 (time) = depth = log(N)이 되는 구조인데,

일단 시간 복잡도에 대해서 먼저 공부를 해야 더욱 정확하게 이해를 할 수 있을 것 같다. 일단 다른 개념들이 더 채워졌을 때,

더 수정을 하거나 추가를 해야할 것으로 보인다.

레벨(Level)

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

 

이것은 DOM 혹은 HTML, CSS에서 든 예시와 비슷하므로 이해가 잘 된다.

레벨은 어디서 쓰이는 걸까? 트리구조의 위치는 상대적인 것을 보이는데, 그 상대적인 것을 표현하기 위해 쓰이는 것일까?

 

순회 방식을 레벨 단위로 정할 수 있다는 것을 알게되었다. 즉, 순회 방식의 설정을 위한 하나의 단위로 사용한다고 생각하면 될 것 같다.

이걸 통해 알게 된 것은 트리구조에서 다양한 순회 방식이 존재한다는 것이다. 그건 아래에서 더 하겠지만,

 

전위 순회, 중위 순회, 후위 순회 방식이 있고, 이것은 Stack(재귀함수, 순환 호출)을 통해 이루어지는 반면,

레벨 순회는 큐를 활용하여 순회된다는 것이다.

높이(Height)

트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.위 그림에서 H, I, E, F, J의 높이는 0이고, D와 G의 높이는 1이다. B와 C의 높이는 2이다. 이때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가진다. 따라서, 루트 A의 높이는 3이다.

 

이것도 상대적인 위치를 표현하기 위해 존재하는 단위로 보인다. 깊이로도 할 수 있지만, 시작 기준점을 어디로 두느냐에 따라 달라지는 것으로 보인다.

서브 트리(Sub tree)

트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부른다. (D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리이다.

 

자료구조는 자료의 집합을 구조화하고, 이를 표현하는 데에 초점이 맞춰져 있다. 사람이 사용하기에 편리하려고, 사용하기 좋으려고 만들어진 것이 자료구조이다. 즉, 저렇게 상대적으로 표현을 해주는 것도 사람이 그 자료구조의 위치를 파악하는데 있어 더욱 용이하게 하기 위해 약속을 한 것이 아닐까?

 

BST(Binary Search Tree)

위의 트리구조는 편리한 구조를 보여주는 것 외에도 효율적인 탐색을 위해 사용되기도 한다.

그 탐색의 방식에 따라 다양한 이름으로 불리기도 하는데, 수많은 트리의 모습 중, 가장 간단하고 많이 사용하는 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)에 대해 정리한다.

 

이진트리(Binary tree)란 자식 노드가 최대 두 개인 노드들로 구성된 트리를 말한다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.

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

오른쪽 부터 정 이진트리, 포화 이진트리, 완전 이진트리

 

정 이진 트리	Full binary tree	각 노드가 0 개 혹은 2 개의 자식 노드를 갖는다.
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있고(두개의 노드가 다 이어져있는 형태), 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있는 상태
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고,

모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

 

 

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야할 문제이다.

 

이런 문제가 발생하게 되면, 선형구조의 탐색과 검색 속도가 비슷해질 수도 있다. 즉, 트리구조를 통해 얻을 수 있는 이점이 거의 제로가 된다는 것과 동일하다는 것.

 

이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

 

AVL Tree를 방안을 쓰면 되는 것일까?

찾아보니 스스로 균형을 유지한다고 하고

(이 방안은 높이를 최소로 유지시키는 조건을 넣어줌으로 인해 구현된다고 한다.)

→ 이진검색트리가 한쪽에 치우치지 않게 해줌
→ 시간복잡도 log값 보장

 

위의 방식을 쓰면 저 2가지의 장점이 있지만, '레드-블랙 트리만큼 효율이 좋지 않아 자주 쓰이지는 않는다고 한다.'

 

Red-Black-Tree

 

레드-블랙 트리 역시도 이진검색트리가 한쪽에 치우치지 않게 해준다.

 

https://zeddios.tistory.com/237

알고리즘 ) Red-Black Tree

와 이건 글을 봐도 이해가 안돼서 일단은 링크를 걸어뒀고, 세세히 찬찬히 개념들이 더욱 많이 들어왔을 때, 봐야할 것 같다...