스택, 큐, 힙, 트리

스택과 큐 모두 선형 자료구조이다.

Stack

• LIFO, FILO의 특성을 가진다. (Last In First Out)
• 빈 스택에서 원소를 꺼내려고 하면 stack underflow, 스택이 제한 크기를 넘기느 경우 stack overflow.

Queue

• FIFO의 특성을 가진다. (First In First Out)

Deque

• Double-Ended Queue.
• 앞과 뒤 모두에서 삽입과 삭제가 가능하다.
• 머리와 꼬리에서 삽입/삭제가 이루어지기 때문에 doubly linked-list를 사용한 구현이 가능하다.

Priority Queue

• 큐에서는 먼저 들어온 데이터가 먼저 나갔다면, 우선순위 큐에서는 우선순위가 큰 순서로 나가게 된다.
• 주로 힙을 통해 구현된다.

Tree

트리는 비선형 자료구조이다.

• 계층적 관계를 표현한다.
• 트리는 노드로 구성된다.
• 하나의 루트 노드를 가지며, 모든 노드는 0개 이상의 자식 노드를 가진다.
• 자식이 0개인 노드를 Leaf Node (또는 Terminal Node)라 한다.
• Leaf Node를 제외한 모든 노드를 Internal Node라 한다.
• 노드와 노드는 간선(edge)로 연결된다.
• 트리에는 사이클이 존재하지 않는다. (계층적이다.) 즉 방향성 역시 단방향이다.
• 트리는 그래프의 한 종류다. 즉 Directed Acyclic Graph (방향성을 가진 비순환 그래프)
• 각 높이별로 숫자를 매기는데, 이를 레벨이라 한다. 루트 노드의 레벨은 0이다.
• 트리의 최고 레벨을 트리의 높이(height)라고 한다.

Binary Tree

• 모든 노드의 자식 노드가 2개 이하인 트리다. 재귀적으로 정의하면, 이진 트리를 두 개의 서브 트리로 가지는 트리다. 즉 이진 트리의 서브 트리들 역시 이진 트리다.
• 모든 노드의 자식 노드가 2개 이하이기 때문에, 공집합 역시 이진트리다. (이 조건은 재귀를 위해서도 필요하다)

포화 이진 트리 (Perfect Binary Tree)

모든 레벨이 꽉 찬 이진 트리.

완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외하고는 포화 이진 트리이며, 마지막 레벨의 노드가 left부터 순서대로 꽉 차있는 이진 트리.
즉, 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리.

정 이진 트리 (Full Binary Tree)

트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 이진 트리. 즉 1개의 자식만을 가지는 노드가 없는 트리.

힙 (Heap)

• 완전이진트리 (Complete Binary Tree) 형태의 자료구조. 최대힙, 최소힙이 있다.
• 최대힙은 각 노드의 값이 해당 노드의 자식들보다 크거나 같은 완전 이진 트리다. 따라서 루트 노드의 값이 가장 크다.
• 최소힙은 각 노드의 값이 해당 노드의 자식들보다 작거나 같은 완전 이진 트리다. 따라서 루트 노드의 값이 가장 작다.
• 루트 노드 제거 시, 가장 마지막 노드를 루트 노드로 대체시킨 후 자식 노드와의 비교를 통해 제자리를 찾아 간다. (heapify)
• 새로운 노드 추가 시, 가장 마지막 노드로 추가하고, 부모 노드와의 비교를 통해 제자리를 찾아간다. (heapify)

이진 탐색 트리 (Binary Search Tree)

• 모든 키들은 유일하다. (중복되지 않는다.)
• 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 즉, 오른쪽 > 부모 > 왼쪽
• 모든 서브트리들 역시 이진 탐색 트리다.
• 저장 순서에 따라 편향 트리 (Skewed Tree)가 될 수 있다. 이는 시간 복잡도 측면에서 안좋은 영향을 미친다. 이를 해결하기 위한 방법으로 Rebalancing이 있다.
• 키의 탐색은 부모 노드부터 크기를 비교하며 해당 노드의 키보다 작을 시 왼쪽 서브 트리, 클 시 오른쪽 서브 트리를 탐색한다.
• 삽입의 경우, 탐색을 실패한 위치가 삽입의 위치가 된다. (즉 이미 키가 존재할 경우 삽입은 불가능하다.)
• 삭제의 경우, 세 가지 경우로 나뉜다.
  1) leaf node인 경우
  단순히 해당 노드의 부모와의 연결을 끊으면 된다.
  2) 하나의 서브트리를 가지는 경우
  해당 노드를 삭제 후 서브 트리를 부모 노드에 붙여준다.
  3) 두 개의 서브트리를 가지는 경우
  오른쪽 서브트리에서 가장 작은 값, 또는 왼쪽 서브트리에서 가장 큰 값을 삭제된 자리로 옮긴다.

힙 vs 이진 탐색 트리?

• 힙은 완전 이진 트리이지만, 이진 탐색 트리는 별도의 정해진 형태가 없다. 따라서 이진 탐색 트리는 편향될 수 있다.
• 힙은 부모와 자식간의 크기만을 유지하지만, 이진 탐색 트리는 부모와 형제끼리 크기를 유지한다. (오른쪽 > 부모 > 왼쪽)

시간복잡도

스택

• 삽입, 삭제 시 모두 top의 데이터에 대해 수행하기 때문에 O(1)의 시간복잡도를 가진다.
• 특정 데이터를 탐색하기 위해서는 top부터 해당 데이터를 찾을 때까지 해야하기 때문에 O(n)의 시간복잡도를 가진다.

큐

• 삽입 시 무조건 마지막에, 삭제 시 무조건 front의 데이터에 대해 수행하기 때문에 O(1)의 시간복잡도를 가진다.
• 특정 데이터를 탐색하기 위해서는 front부터 해당 데이터를 찾을 때까지 해야하기 때문에 O(n)의 시간복잡도를 가진다.

덱

• 삽입과 삭제 모두 front/rear에서 이루어지기 때문에 O(1)의 시간복잡도를 가진다.
• 특정 데이터를 탐색하기 위해서는 front부터 (또는 rear부터) 해당 데이터를 찾을 때까지 해야하기 때문에 O(n)의 시간복잡도를 가진다.

우선순위 큐 (힙)

• 루트 노드의 값이 최대(최소힙의 경우 최소)이기 때문에 최대값(최소값)을 찾기 위해 O(1)의 시간복잡도를 가진다.
• 루트 노드 제거 시, 새로운 루트 노드를 위한 비교 과정이 최대 트리의 높이만큼 요구되기 때문에 O(log n)의 시간복잡도를 가진다.
• 새로운 노드 추가 시, 위치를 찾기 위한 비교 과정이 트리의 최대 트리의 높이만큼 요구되기 때문에 O(log n)의 시간복잡도를 가진다.

이진 탐색 트리 (Binary Search Tree)

• 탐색을 최대 높이만큼 수행하기 때문에 O(h)의 시간복잡도를 가진다. 이 때, 트리가 balanced 된 경우 O(log n)을 가지지만, 편향된 경우 O(n)을 가지게 되어 일반적인 배열과 차이가 없어진다.
• 삽입은 탐색을 실패한 자리에 수행되기 때문에 탐색과 시간복잡도가 같다.
• 삭제의 경우 역시 해당 노드를 탐색해야 한다. 이는 O(h)가 소요된다. 이후, 단말 노드 또는 서브 트리가 1개인 경우 단순히 붙이는 작업만 하면 되기 때문에 O(1)이 된다. 그러나 만약 서브 트리가 2개인 경우, 서브 트리에서의 탐색 작업만큼 시간복잡도가 요구된다. 최악의 경우 이는 O(h)이다. 결국 세 가지 경우 모두 탐색을 위해 O(h)가 요구되고, 즉 탐색과 같아진다.