자료구조 기초 정리 (시간 복잡도, 추상 데이터 타입, 선형 자료구조, 트리)

시간 복잡도 : 인스턴스에 따른 실행 시간 변화 추이를 나타내는 척도

추상 데이터 타입 (ADT) : 자료구조의 명세서, 사용 설명서 같은 것. 데이터가 저장되는 방식과 데이터의 인터페이스 역할을 하는 메소드들의 정의로 이루어져 있다.

배열(Array) : 탐색 시간이 O(1)이지만, 삽입과 삭제가 worst case의 경우 O(n)이다.
링크드 리스트(Linked List) : 삽입과 삭제 시간이 O(1)이지만, 탐색 시간이 worst case의 경우 O(n)이다.

스택과 큐 : 둘 다 선형 자료구조이다.
스택(Stack) : LIFO(Last In First Out) 방식의 자료구조.
큐(Queue) : FIFO(First In First Out) 방식의 자료구조. 

트리(Tree) : 비선형 자료구조. 계층적 관계로 데이터를 저장한다.
이진트리(Binary Tree) : 자식 노드가 최대 2개인 트리. 재귀적으로 정의하면 루트 노드를 중심으로 2개의 서브 트리로 나뉘며, 두 서브 트리도 모두 이진 트리이다.

포화 이진트리(Perfect Binary Tree) : 모든 레벨이 꽉 찬 이진트리.
완전 이진트리(Complete Binary Tree) : 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워진 이진트리.
정 이진트리(Full Binary Tree) : 모든 노드가 0개 혹은 2개의 자식 노드를 가짐.

이진 탐색트리 BST(Binary Search Tree) : 탐색 시간이 효율적이도록 규칙을 준수하며 데이터를 저장한 트리.
노드에 저장된 모든 키는 유일하고, 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키 순서로 대소 관계를 가지며, 서브트리들도 모두 이진탐색트리이다.
탐색 시간은 O(log n)이 되며, 트리의 높이를 h라고 하면 O(h)라고 할 수 있다.
이진 탐색트리는 편향 트리(skewed tree)가 될 수 있다는 문제가 있다. 이러면 최악의 경우 시간 복잡도가 O(n)에 비슷해진다. 이를 위해 트리의 균형을 잡는 기법을 Rebalancing이라고 한다.

이진 힙(Binary Heap) : 배열에 기반한 완전 이진 트리. 맥스 힙(Max Heap)과 민 힙(Min Heap)이 있다. 맥스 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같고, 민 힙은 그 반대이다.
맥스 힙은 최대값을 찾는 시간이 O(1)이다. 그러나 삽입과 삭제 시 힙의 구조를 유지하기 위한 연산에 O(log n)의 시간이 든다.