Data Structure

 목차

• Array vs Linked List
• Stack and Queue
• Tree
• Binary Heap
• Red Black Tree
• Hash Table
• Graph

Array vs Linked List

Array

Array는 논리적 저장순서와 물리적 저장순서가 일치한다. index를 통해 해당 원소에 접근할 수 있다. 그렇기에 찾고자하는 원소의 인덱스 값(탐색)을 알고있으면 O(1)에 해당원소로 접근 가능하다. 

삽입/삭제 과정에서는 해당 원소에 접근해 작업을 완료한뒤 , 또 한가지의 작업(삽입/삭제)을 추가적으로 해야하기 때문에 시간이 더 걸린다. 배열의 원소 중 어느 원소를 삭제했다고 했을 때 , 삭제한 원소보다 큰 인덱스르 갖는 원소들을 shift 해줘야 하기에 시간복잡도는 O(n)이 된다. 삽입의 경우도 마찬가지이다.

Linked List

위의 Array의 문제점을 해결하기 위한 자료구조가 Linked list 이다. 각각의 원소들은 노드 간 연결로 인해 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이부분만 다른 값으로 바꿔주면 삭제/삽입을 O(1)만에 해결할 수 있는 것이다.

하지만 원하는 위치에 삽입을 하고자 하면 원하는 위치를 찾는 과정(탐색)에 있어서 첫번째 원소부터 다 확인해봐야 한다. 이 과정으로 원하는 위치에 삽입/삭제를 하고자 했을때 발생하는 시간복잡도는 O(n)이다. Array와 달리 논리적 저장순서와 물리적 저장순서가 일치하지 않기 때문이다. 

 

Stack and Queue

Stack과 Queue는 선형구조로 자료를 구성하는 원소들은 순차적으로 나열시킨 형태를 가진 자료구조이다.

Stack

LIFO(Last In First Out)/FILO(First In Last Out)로 먼저 들어간 원소는 나중에 나오고 나중에 들어간 원소가 먼저 나오는 특징을 가지고 있다.

Queue

FIFO(First In First Out)로 , 먼저 들어간 원소가 먼저 나오는 특징을 가지고 있다. Stack과는 반대 성질을 가지고 있다.

 

Tree

트리는 비선형 자료구조로 하나의 자료(Root) 뒤에 여러개의 자료가 존재할 수 있는 형태를 가진 자료구조이다.

트리에서는 각 층별로 숫자를 매겨 이것을 트리의 Level이라고 한다. 레벨의 값은 0부터 시작해 루트의 노드레벨을 0이다.트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

 

Tree의 구성요소

- Node(노드) : 트리를 구성하고 있는 요소를 의미한다.

- Edge(간선) : 노드와 노드를 연결하는 선을 의미한다.

- Root Node(루트 노드)  : 트리 구조에서 최상위에 있는 노드를 의미한다.

- Terminal Node(leaf Node)(단말 노드) :  자식이 없는 노드르 의미한다.

- Internal Node(비단말 노드) : 적어도 하나의 자식을 가지는 노드를 의미한다.

 

Binary Tree(이진트리)

루트 노드를 중심으로 2개의 서브 트리로 나뉘어진다. 그리고 재귀적으로 나뉘어진 트리도 모두 이진트리여야 한다. 모든 노드가 최대 2개의 자식을 가지는 트리 자료구조이다.

Perfect Binary Tree(포화 이진 트리)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다.

Complete binary tree(완전 이진 트리)

위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다. 

Full Binary Tree(정 이진 트리)

모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.

 

Binary Tree의 종류

BST(Binary Search Tree)

이진 탐색 트리는 이진 트리의 일종으로 데이터를 저장하는 규칙이 있다. 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다. 이진탐색 트리의 탐색 연산은 O(logn)의 시간 복잡도를 갖는다. 트리의 높이를 H라 한다면 O(H)라는 시간 복잡도를 갖게되는데 H=log2(N+1)-1 라는 식으로 결과적으로 O(logn)이라는 시간복잡도를 갖게된다.

 

    이진 탐색 트리의 데이터를 저장하는 규칙

1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.

2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.

3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.

4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

 

Binary Heap(이진 힙)

Tree 형식을 가지고 있는 자료구조의 일종이며, 배열에 기반한 Complete Binary Tree(완전 이진 트리)이다. 배열에 트리의 값을 넣어줄때 0번은 건너뛰고 1번 index부터 루트노드가 시작된다. Heap에는 Max Heap, Min heap으로 두 종류가 있다.

Max Heap은 각 노드의 값이 해당 children의 값보다 크거나 같은 complete Binary Tree를 말한다.(Min Heap은 Max Heap과는 반대이다.)

Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complexity 이 O(1)이다. 그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다.(Min heap 에서는 최소값을 찾는데 소요되는 연산의 time complexity 가 O(1)이다.)

Red Black Tree

BST(이진 탐색 트리)를 기반으로 하는 트리 형식의 자료구조이다. RBT에 데이터를 저장하게 되면 Search,Insert,Delete에 O(logn)의 시간복잡도가 소요된다. 동일한 노드의 개수일 때, depth를 최소화해 시간복잡도를 줄이는것이 핵심이다. 해당 경우는 tree가 Complete Binary Tree 인 경우이다.

 

Red Black Tree (출처: 위키피디아)

    Red Black Tree의 정의

1. 각 노드는 Red or Black이라는 색깔을 갖는다.
2. Root node 의 색깔은 Black이다.
3. 각 leaf node 는 black이다.
4. 어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다.
5. 모든 leaf node에서 Black Depth는 같다. leaf node에서 root node까지 가는 경로에서 만나는 black node의 개수가 같다.

Hash Table

Hash Table은 key,value로  데이터를 저장하는 자료구조 중 하나이다. hash는 배열을 사용해 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. Hash Funcion을 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조이다.

Hash Function

hash function이라는 메소드로 인해 데이터의 고유 숫자 값을 hashcode라고 한다. 저장되는 값들의 key 값을 hash function을 통해서 작은 범위의 값들로 바꿔준다. 하지만 그 결과 동일한 값이 도출될 수도 있어 동일한 key값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는데 이를 Collision 이라 한다.

Resolve Confilct

1. Open Address 방식(개방 주소법)

해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식이다.

2. Separate Chaining 방식(분리 연결법)

동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다.

 

Graph

그래프는 연결되어 있는 원소간의 관계를 표현한 자료구조이다. 트리 또한 그래프이며, 사이클이 허용되지 않는 그래프를 말한다.

Undirected Graph 와 Directed Graph

정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph라하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph라고 한다.

Degree

방향성 없는 그래프에서 각 정점에 연결된 간선의 개수를 Degree라고 한다. 방향성 있는 그래프에서는 간선의 방향성이 존재하기 때문에 Degree가 두개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree라 하고, 들어오는 간선의 개수를 Indegree라고 한다.

Weight Graph 와 Sub Graph

가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다.

부분 그래프는 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

그래프 탐색

깊이 우선 탐색(DFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 

Stack을 이용해 탐색한다. 시간복잡도는 O(V+E)이다. (V:vertex 개수 , E:edge 개수)

너비 우선 탐색(BFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Queue를 이용해 탐색한다. 시간복잡도는 O(V+E)이다. (V:vertex 개수 , E:edge 개수)

Minimum Spanning Tree

방향성 없는 그래프에서 간선들의 가중치 합이 최소인 신장 트리를 말한다. 여기서 신장트리는 하나의 그래프가 있을때, 모든 노드를 포함하면서, 모든 노드들 간에 서로 연결은 되어있되 사이클은 존재하지 않는 부분 그래프를 말한다.

Kruskal Algorithm

비용에 따라 정렬된 간선을 하나씩 선택하며 MST를 찾는 방법이다.

1. 그래프의 간선들을 가중치를 기준으로 오름차순 정렬한다.
2. N - 1개의 간선이 선택될 때까지
   • 가중치가 낮은 간선부터 탐색하면서, 사이클을 형성하지 않으면 간선을 선택한다.
   • 사이클 형성 여부는 union-find 자료구조를 활용하여 판단한다.

union-find : 서로소 집합(중복된 원소가 없는 집합)을 표현하는 자료구조

Prim Algorithm

특정 정점에서 출발하여 정점을 하나씩 선택하며 신장트리 집합을 확장해나가는 방법이다. 

1. 임의의 간선을 선택한다.
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다.
3. 모든 정점이 선택될 때까지 반복한다.

Reference

https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

https://github.com/JaeYeopHan/Interview_Question_for_Beginner