Data structure part.2 - Javascript

1.Graph

Graph는 연결 리스트에서와 유사하게 생각할 수 있다.

A~F는 vertex이다. 각각의 vertex를 연결 리스트의 node라고 생각하고,
vertext 간에 이어진 선은 arc이다. arc는 pointer를 통해서 연결되는 node의 상태를 가시화하였다고 생각한다.
이 떄, 어떤 하나의 vertex가 가지고 있는 arc의 수를 degree라고 한다.

 

vertex 간의 연결 및 방향성
Graph에서는 하나의 vertex가 여러 개의 다른 vertex와 연결될 수도 있으며,
방향이 지정되어 있어도 되고, 지정되어 있지 않아도 된다.
방향성이 있는 경우에, 어떤 vertex로 향하고 있는 arc 개수를 In-degree, 어떤 vertex에서 다른 vertex로 가는 arc 개수를 Out-degree라고 한다.
모든 vertex 간에 arc가 형성되어 있는 그래프를 완전 그래프, 그렇지 않은 그래프를 부분 그래프라고 한다.

 

관련 용어

1) 완전그래프 (complete graph)

=> arc 개수가 최대인 그래프.

- n개 노드의 무방향그래프 : 최대 arc 개수 n(n-1)/2 

- n개 노드의 방향그래프 : 최대 arc 개수 n(n-1)

 

2) 인접 (adjacent)

=> 무방향 그래프에서 노드 a, b에 대하여 arc (a, b)가 있으면 (a, b)는 서로 인접하다고 한다.

 

3) 부속 (incident)

=> 무바향 그래프에서 정점 a, b에 대하여 간선 (a, b)가 있으면 간선 (a, b)는 각 정점에 부속한다고 한다.

 

작동 원리에 대해서 간단히 생각해본다면
연결 리스트의 자료구조를 활용하여 구현할 수 있을 것 같다.

인접 리스트

: n개의 노드가 있을 경우, n개의 연결리스트로 그래프를 표현한다.

그래프의 각 정점에 대하여 정점과 연결된 간선을 노드 한 개 당 한 개의 연결리스트에 저장한다.

결과적으로 전체 연결리스트는 n개가 되며, 이 연결리스트를 배열로 표현한다.

이 때에, 기억하는 간선에는 가중치(weights)를 부여할 수 있는데

가중치는

1) 정점에서 정점으로 가는 거리

2) 정점에서 정점까지 도달하는 비용

등을 의미한다.

 

 

0: 1 //0정점은 1정점과 인접
1: 2 //1정점은 2정점과 인접
2: 0, 3 //2정점은 0과 3정점에 인접
3: 2 //3정점은 2정점과 인접
4: 6 //4정점은 6정점과 인접
5: 4 //5정점은 4정점과 인접
6: 5 //6정점은 5정점과 인접

탐색

1) 깊이우선탐색(Depth First Search)

: 깊이 갈 수 있는데까지 가보는 방문 방법. tree의 preorder traversal을 적용.

1. 하나의 노드 선택
2. 노드 방문 후 필요한 작업한 다음 연결된 다음 노드 찾는다. 현재 방문 노드는 스택에 저장. 2단계를 반복하면서 계속 방문하다가 막히면 3단계로 진행
3. 더이상 방문할 노드가 없으면 스택에서 노드를 빼내고 다음 방문 노드를 찾아서 2단계 과정을 반복

*스택을 이용하고, 노드 방문과 관련하여 초기값은 false이다가 방문하고 나면 true로 바꾸어 판별할 수 있도록.

 

2) 너비우선탐색(Breath First Search)

: 거리가 가까운 곳부터 가보는 방문 방법. tree의 level order tree traversal 적용.

추가 입력 필요 부분

 

 

 

2.Tree
Tree 구조는 DOM을 다루면서 접했던 경험이 있다.

Tree 구조는 cyle(처음과 마지막 정점이 같은 단순경로)이 없고, 연결된 그래프로 루트 노드가 1개 존재하는 그래프이다.

1.Root - 말 그대로 나무의 시작인 뿌리라고 하는 Starting Node.
2.Leveling - Root 밑으로 나무가 가지를 치듯이 단계별로 Node들이 생성된다.
3.ParentNode and ChildNode - D와 H는 부모자식 관계이고, 이 때 D가 부모노드, H가 자식노드가 된다. 자식노드는 Left와 Right로 구분된다.
4.Siblings - ParentNode가 같은 ChildNode들을 일컬어 Siblings라고 한다.
5.LeafNode - 더이상 ChildNode가 없는 node를 지칭한다.

 

사용 예
-Routing
-정렬/검색 알고리즘
-계층 구조
-3D게임에서 어떤 object가 render 되어야 하는지 결정할 때
-.jpeg이나 .mp3 포맷의 파일을 압축할 때

 

주요 용어
-Degree of a node : 해당 노드가 가진 childrenNode의 개수
-Degree of a Tree : 주어진 tree에서 가지는 최대의 degree of node
-Path : sourceNode로부터 destinationNode까지의 연속되는 edge의 순서
-Height of a node : 해당 node로부터 leafNode까지의 최대 path 길이
-Height of a tree : root로부터 측정하는 Height
-Depth of a tree : tree에서 leafNode까지 도달하는 최대의 level

 

특징
-Non-linear 구조
-ordered array의 장점을 결합하여, ordered array만큼 검색이 빠름
-삽입과 삭제가 linked list만큼 빠름
-간단하고 빠름

 

B-tree
트리 자료구조의 일종. Binary Tree를 확장하여 하나의 노드가 가질 수 있는 자식 노드의 최대 갯수가 2보다 큰 트리 구조.

기본 개념은 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경가능하다.
항목의 삽입, 혹은 삭제 시에 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 다른 노드와 합쳐진다.
자식 노드의 최소 및 최대수는 일반적으로 특별한 구현에 대해서 결정되어 있다.

예를 들어, 2-3 B-트리(혹은 단순히 2-3 트리)에서 각 내부 노드는 2 또는 3개의 자식 노드를 가질 수 있다.

 

부적절한 상태의 노드
: 만약 허용되지 않은 수의 자식 노드를 가질 경우, 해당 내부 노드는 부적절한 상태에 있다고 한다.

 

작동 원리에 대해서 간단히 생각해본다면

• mother(node, tree) : tree 내에 있는 해당 노드 node의 parentNode를 return. 만약 해당 노드가 root라면 return null
• LeftChild(node, tree) & RightChild(node, tree) : tree 내에 있는 해당 노드 node의 Left 혹은 Right childNode를 return. 만약 해당 childNode가 없다면 return null.
• Info(node, tree) : tree 내의 node 노드가 저장하고 있는 정보를 return.
• Sibling(node, tree) : node 노드와 sibling 관계인 노드를 return. sibling이 없다면 return null.
• Root(tree) : 해당 tree가 비어있지 않다면, rootNode를 return.
• Size(tree) : 해당 tree 내의 node 개수를 return.
• MakeEmpty(tree) : 비어있는 tree를 새로 생성.
• SetLeft(S, tree) : sub tree인 S를 tree의 left에 붙임.
• SetRight(S, tree) : sub tree인 S를 tree의 right에 붙임.

탐색
-Preorder(tree) : tree의 모든 노드들을 preorder로(root -> left sub tree -> right sub tree) 순회한다.
-Postorder(tree) : tree의 모든 노드들을 postorder(left sub tree -> right sub tree -> root)로 순회한다.
-In-order(tree) : tree의 모든 노드들을 in-order(left sub tree -> root -> right sub tree)로 순회한다.

삽입
1.노드가 삽입될 위치를 찾아 해당 부모 노드에 삽입.
2.부적절한 상태의 노드가 없다면, 삽입 과정 종료.
3.만약 어떤 노드가 너무 많은 항목 갖고 있다면, 두 노드로 분리시킨다. 이 과정을 트리를 타고 올라가며 반복적으로 진행한다.
만약의 경우 root 노드를 분리했다면, 새로운 루트 노드를 만든다.

 

 

3.Hash-Table
해시테이블이란,
해시함수를 사용하여 키를 해시값으로 매핑하고,
이 해시값을 색인(index) 혹은 주소로 삼아 데이터의 값을 키와 함께 저장하는 자료구조이다.
이 때, 데이터가 저장되는 곳을 bucket, 또는 slot이라고 한다.
기본적인 연산으로는 삽입, 삭제, 탐색이 있다.

• 해시함수(hash function) : 데이터를 효율적으로 관리하기 위하여, 임의의 길이의 데이터를 고정된 길이의 데이터로 mapping하는 함수
• 키(key) : mapping하기 이전의 원본 데이터 값
• 해시값(hash value) : mapping한 후의 데이터 값
• 해싱(hashing) : mapping하는 과정

위의 각 버킷에는 아래와 같이 데이터가 저장된다.

Index(Hash Value)	Data
01	(Lisa Smith, 521-8976)
02	(John Smith, 521-1234)
...	...

보통의 경우, 해시값의 개수보다 키 값의 개수가 많아서
키 값은 다르지만, 해시값이 일치하게 되는 해시충돌(collision) 발생

장점)

• 적은 리소스로 많은 데이터 효율적 관리
• 색인(index)에 해시값을 사용하여, 검색과 삽입/삭제를 O(1)으로 엑세스 (키 값 입력 -> 해싱 -> 해시값으로 처리

작동 원리에 대해서 간단히 생각해본다면
1)사용하고자 하는 데이터를 key 값으로서 가져온다.
2)임의의 hash function을 통하여 가져온 key 값이 특정 hash 값으로 변환되어 기억된다. 예를 들면 index.
3)버킷의 모음을 가지는 객체 안에 hash 값과 연동된 버킷을 생성하여, hash 값을 key로 가지고, 기존에 mapping하기 이전의 data를 value로 저장한다.
4)이 후, 특정 index 혹은 key 값으로 검색 시에는 3)에서 만들었던 버킷을 이용하여 저장되었던 값을 가져온다.