CS - Data Structure(Array, Linked List, Tree)

1. Array vs Linked List

	Array	Linked List
요소 접근 시간	O(1)	O(n)
삽입, 삭제 연산	O(n)	O(n)

※ Linked List의 실제 삽입, 삭제 연산 수행시간은 O(1) 이지만 삽입, 삭제 연산을 수행 할 target value를 찾기 위한 시간이 O(n)만큼 소요되므로 삽입, 삭제 연산은 O(n)의 시간복잡도를 가진다.

 

해당 표만 보면 Linked List 보다는 Array를 사용하는것이 시간적 이득을 가지지만, Linked List는 Tree 구조로 사용되었을 때 유용하게 사용된다. 또한 선언시에 최대 크기가 고정되어버리는 Array에 비해 Linked List는 새로운 Node를 객체로 만들어 최대 크기를 유연하게 조정 할 수 있다.

 

2. Stack vs Queue

	Stack	Queue
데이터 처리 방식	Last in First Out (LIFO)	First in First Out (FIFO)
pop left 시간복잡도	O(n)	O(1)
pop 시간복잡도	O(1)	O(n)

JAVA에서 Stack에 pop left 메소드가 있거나 Queue에 pop 메소드가 있는것은 아니지만, 이해의 편의성을 위해 위와 같이 기록하였다.

pop left -> 첫번째 값을 뽑아오는 행위

pop -> 마지막 값을 뽑아오는 행위

※ Queue는 JAVA Collection 클래스에서 Interface 형식이므로, Priority Queue와 같이 구현된 클래스를 이용해 사용해야 한다.

 

3. Tree - 비선형 자료구조

root node : 최상단 노드

Edge(간선) : 각 노드를 이어주는 선

Internal node(내부 노드) : 루트 노드, 단말 노드가 아닌 노드들. 루트 노드가 아닌 노드들 중 자식 노드를 가지고 있는 노드

Terminal Node(leaf 노드라고도 하며, 단말 노드) : 자식이 없는 노드들.

Descendant leaves : 모든 단말 노드를 가리킴. 

 

3 - 1) Binary Tree(이진 트리)

각 노드의 자손 노드가 2개 이하인 트리.

루트 노드를 중심으로 두개의 서브 트리로 나뉜다. 각 서브트리들도 모두 이진 트리이어야 함.

 

3 - 2) Binary Search Tree(이진 탐색 트리)

각 노드의 key를 기준으로 위치가 결정된 이진 트리.

1. 왼쪽 자식 노드의 key는 부모 노드의 key보다 작아야 한다.

2. 오른쪽 자식 노드의 key는 부모 노드의 key보다 커야 한다.

 

이진 탐색 트리의 평균적인 탐색 연산 시간 복잡도는 O(log n)이다.

-> 탐색 대상인 모집단의 수가 1/2씩 줄어들기 때문.(이진 트리이기 때문에)

하지만, 이진 탐색 트리의 루트 노드가 적절하지 않은 값인 경우(최악의 상황 : 루트 노드의 key가 해당 이진 탐색 트리의 key중 가장 클 경우) 탐색 연산의 시간 복잡도는 O(n)이 된다.

이런 이진 탐색 트리를 편향 트리라고 함.

 

이러한 편향 상태를 방지하기 위해, Red Black Tree가 등장함.

 

3 - 3) Red - Black Tree

레드 - 블랙 트리는, 이진 탐색 트리의 편향 상태를 해결해주는 이진 탐색 트리의 형태이다.

- 레드 블랙 트리의 루트 노드 - 단말 노드 최대 경로 길이와 루트 노드 - 단말 노드 최소 경로 길이의 차는 2를 넘지 않는다. 이 상태를 Blanced한 상태라고 함.

 

Red - Black Tree의 특징

1. 부모 노드는 Black Node.

2. 모든 단말노드들은 Black Node.

3. 만약 Red Node가 있다면, 해당 Red Node의 모든 자식 노드들은 Black Node이다.

4. 한 노드에서 모든 단말 노드로가는 각각의 최단 경로에는 같은 수의 Black Node들을 가지고 있다.

3 - 4) Binary Heap

Max heap, Min heap이 있으며 각각 최댓값 pop, 최솟값 pop에 O(1) 시간복잡도를 가짐.

하지만, pop 연산을 수행 할 경우 다시 heapify 연산을 수행해야 하므로 실제 최댓값, 최솟값 pop 연산의 시간복잡도는 O(log n)이다.