Data Structure Graph, Tree, BST

Graph

Graph란 node와 node를 연결하는 간선(edge)을 하나로 모아 놓은 Data Structure이다.

하지만 모든 노드들이 전부 서로 연결되어 있는 것은 아니다.
양방향으로 통행이 가능한 무방향 그래프와, 일반통행만 가능한 방향 그래프가 있다.무방향 = 양방향 통행

 

• addNode(node) - 그래프에 노드를 추가합니다.(Methods)
• addEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 추가합니다.(Methods)
• removeNode(node) - 그래프에서 노드를 삭제합니다.(Methods)
• removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.(Methods)
• hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.(Methods)
• contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.(Methods)
• edge : 위치 간의 관계(노드와 노드를 연결해주는 property이다.

Graph Pseudocode.

 

Tree

트리는 노드로 구성된 계층적 자료구조입니다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있습니다. 가계도처럼 맨 처음의 Root노드가 있고 그 아래로 자식노드들이 생기는 구조. 오른쪽으로 뻗은 가지들은 부모노드보다 값이 크고 왼쪽으로 뻗은 가지들은 부모노드보다 값이 작다(그림에서는 G가 가장 큰 노드, H가 가장 작은 노드)

 

트리 구조와 관련하여 반드시 알아야 할 개념을 소개합니다.

• A, B, C, D 등 트리의 구성요소를 노드(node) 라고 합니다.
• 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root라고 합니다.
• 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 합니다.
• 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다.
• 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 입니다.
• 노드와 노드를 잇는 선을 edge 라고 합니다.
• 자식이 없는 노드는 leaf 라고 합니다.

 

• insertNode(value) - 트리에 노드를 추가합니다.
• contains(value) - 트리에 해당 노드가 존재하는지 여부를 반환합니다.

depth와 height는 어떻게 다른가요?

 

Tree 의 height는 root로부터 얼만큼 내려와 있는지를 확인한다.

Tree 의 depth는 요소에서부터 시작하며 요소에서부터 root까지의 거리를 재는 것이다. 정확하게는 트리 안에서의 특정 노드의 깊이라고 말할 수 있다.

 

트리와 그래프의 차이점은 무엇인가요?

 

graph

2개 이상의 경로가 가능하며 무방향에서 양방향으로도 가능하다.

자기 자신을 돌 수 있고, loop도 가능하며, 루트 노드 개념이 없고, 부모-자식 개념도 없다.
그래프 순회는 DFS, BFS로 이루어져 있으며, 그래프는 네트워크 모델로 되어있다.

 

tree

트리는 그래프의 특별한 케이스이며, "최소 연결 트리"라고도 불린다.

루트 노드 개념이 있고, 부모-자식 개념도 있고 자기 자신을 돌 수 없음은 물론이고 loop 순환도 불가하다.
부모-자식 관계의 흐름은 상하이며, 트리의 순회는 전위, 중위, 후위 순환으로 이어지고, 이것들은 모두 그래프의 DFS, BFS 안에 있다.
트리에는 종류가 많다. (이진트리, 이진탐색트리, AVL트리, 힙트리 등) 트리는 계층 모델이다.

 

Tree Pseudocode.

 

Binary Search Tree

이진 탐색 트리는 최대 2개의 자식만 갖는 트리입니다.

트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 갖습니다.

이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재합니다.

노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재합니다. (그림 참조)

이진 탐색 트리를 순회하는 방법은 크게 깊이 우선 탐색 (DFS, Depth-First Search)와 너비 우선 탐색 (BFS, Breadth-First Search) 알고리즘이 존재하는데, 지금은 깊이 우선 탐색의 다양한 방법에 집중합시다.

 

• insert(value) - 이진 탐색 트리에 노드를 추가합니다.
• contains(value) - 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환합니다.
• inorder(callback) - 이진 탐색 트리를 중위순회 합니다.

깊이 우선 탐색 방법 DFS(depth-first search)

하나의 정점으로 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법인데요, 어떠한 방향으로 쭉 뻗어진 것을 끝까지 탐색 후, 더는 길이 없다고 생각하게 되면 다음으로 넘어갑니다. 이 방법은 '모든 노드를 돌아보고 싶을 때' 사용을 합니다. 단순 검색은 너비 우선 탐색보다 느리지만 조금 더 간단하다는 장점이 있습니다.

너비 우선 탐색 방법 BFS(Breadth-First Search)

깊이 우선 탐색 방법과 반대의 개념으로, 하나의 정점으로 시작해서 그 정점과 맞닿아 있는 가지들을 우선적으로 본 후, 그 다음 줄에 있는 가지들, 그 다음 줄에 있는 가지들을 차례대로 보는 법을 말합니다. 두 노드 사이의 최단 경로, 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다.

 

DFS는 재귀로 움직일 수 있는 반면에 BFS는 재귀로 움직일 수 없습니다.

DFS는 스택을 사용하지만 BFS는 큐를 사용합니다.

DFS는 이진트리의 전위, 중위, 후위 탐색에 사용됩니다.

 

전위 순회(Preorder Traversal): 부모 → 좌 → 우

중위 순회(Inorder Traversal): 좌 → 부모 → 우

후위 순회(Postorder Traversal): 좌 → 우 → 부모

완전 이진 트리 VS 정 이진 트리 VS 포화 이진 트리

• 완전 이진 트리 (complete Binary Tree)
  트리의 모든 높이에서 노드가 꽉 차 있는 모든 트리를 말합니다. 마지막 노드를 제외한 모든 노드들이 두 개씩 전부 채워져 있어야 하며, 만약 하나가 비워져 있다고 하더라도 오른쪽이 비워져 있어야 합니다.

• 정 이진 트리 (full binary tree)
  모든 노드가 0개 또는 2개의 자식 노드를 가지고 있어야 합니다. 1개를 가지고 있는 것은 정 이진 트리가 아닙니다.

• 포화 이진 트리 (Perfect Binary tree)
  완전 이진 트리와 정 이진 트리를 합친 건데요, 영어를 그대로 직역한 것처럼.. Perfect, 꽉 차 있어야 되는 트리입니다. 마지막을 제외한 모든 노드가 두 개의 자식 노드를 가져야 합니다.

BST Pseudocode.