Data-Structure Series (Graph, Tree, Binary Search Tree)

Graph(abstract data type)

추상 데이터 유형을 구현하기 위한것.

구성

vertex(node), arc(edge)로 구성되어있다.
다른 버텍스로 부터 오는 아크를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라 부른다. 또한 방향 그래프(화살표유), 무방향 그래프(화살표무)로 나눈다.

이때 모든 버텍스가 아크로 연결된 그래프를 완전 그래프, 부분집합을 부분 그래프라 힙니다.

그래프를 코드로 표현하는 방법에는 크게 두 가지로 나누는데

• 이차원배열 =>
  공간을 많이 차지(버텍스 개수(V)의 제곱에 해당하는 공간을 차지)
  but, 간단함.
• 연결 리스트 =>
  공간을 적게 차지(버텍스 개수와 아크 개수(E)의 합에 해당하는 공 간만 차지 but, 복잡함.

DFS

Depth First Search의 약자로 깊이 우선 탐색이라 한다.
버텍스의 자식들을 우선으로 탐색한다.

버텍스 옆의 숫자는 탐색 순서이다.

BFS

Breadth First Search의 약자로 너비 우성 탐색이라한다.
버텍스의 형제들을 우선으로 탐색한다.

Tree

생각과는 반대로 Root로 지었으면 더 나았을것 이라 생각했다.
거의다 HTML tag를 기반으로 설명하는데 그림을 보면 무슨말인지 이해 될것이다.

그렇죠? 일단 Root인 Document부터 시작하여 아래로 자식 노드들이 뻗어나가는 구조이다. 아이러니하게 위에가 root 가장 아래 자식들이 leaf(자식이 없는 노드)다. 말 그대로 거꾸로 세웠다고 생각하면 편할듯.
그래서 노드와 노드를 이어주는것을 branch 혹은 edge라 불리우고 path는 root에서 child node 까지 가는 경로를 말하며, height은 부모 노드에서 자식 노드 사이의 edge개수를 말한다.

Structure & Time complexity

insertion:

노드를 추가할때, 원하는 위치의 노드에 자식으로 추가를 한번에 할수 있다. O(1)

Deletion, Search:

삭제할 노드를 찾기위해선 자식들을 하나씩 탐색하면서 내려가야하는데, 최악의 경우 leaf까지 내려가서 제거하거나 찾아야 한다. O(n)

Binary Search Tree

이진 검색 트리라고 부르며 앞서 트리와 같은 구조로 자식이 2개 이하로만 존재하며, 순서가 있고(왼쪽은 작은 숫자, 오른쪽은 큰 숫자) 일정한 규칙으로 뻗어나가는 데이터 구조이다.
worst case로는 노드가 한쪽으로 뻗는 경우가 있다. O(n)
이를 위해 AVL Tree, Red Black Tree 가 있다.O(logN)

Structure & Time complexity

insertion, deletion, search/ O(logN)

왼쪽은 작은 숫자, 오른쪽은 큰 숫자로 일정한 규칙으로 branch가 뻗어 나간다면, 원하는 노드를 추가, 삭제, 검색한다고 할때 노드가 기준이 되는 한쪽을 잘라 검색하고 없다면, 또 그것의 반을 잘라 검색하게된다.