Array와 LinkedList
Array는 메모리 상에서 하나의 묶음으로 고정되어있는 그룹이라면, LinkedList는 메모리와 상관없이 각각의 요소들이 동적으로 이어져있는 그룹!
이러한 차이점에 의해 Array는 빠른 접근 속도와 연속된 메모리 사용이 장점이지만, 크기 고정으로 삽입 및 삭제가 비효율적이고,
LinkedList는 삽입/삭제가 효율적이지만, 접근 속도가 느리며 메모리 오버헤드가 발생할 수 있음!
Stack과 Queue
Stack과 Queue는 데이터를 저장하거나 삭제(사용)하는 순서의 차이가 있다!
Stack은 자료를 LIFO(후입선출) 방식으로 팬케이크처럼 데이터를 쌓아서 사용하고,
Queue는 자료를 FIFO(선입선출) 방식으로 톨게이트마냥 데이터를 순차적으로 통과하듯 사용한다
Graph와 Tree
그래프와 트리는 Node와 Edge로 구성되어있는 데이터 구조로, 아래와 같은 차이점이 있습니다
-
순환 : 그래프는 순환이 있을 수 있지만, 트리는 순환이 없다!
-
방향성 : 그래프는 방향성이 있을 수도 있고 없을 수도 있지만, 트리는 일반적으로 방향성이 있다 (부모 -> 자식)
-
연결성: 그래프는 모든 노드가 연결되어 있지 않아도 되지만, 트리는 모든 노드가 연결되어 있다
-
시작지점(루트 노드): 트리는 하나의 루트 노드가 있지만, 그래프는 루트 노드가 없다 ( 방향성과 연관되어 있는 느낌이죠? )
약간의 비유를 하자면 Graph와 Tree는 직사각형(Graph)과 정사각형(Tree)의 관계와 비슷한 것 같다!
Binary Heap/Tree + Red-black Tree(자가 균형 이진 탐색 트리)
Binary Tree(이진 트리)는 모든 노드는 최대 2개의 서브트리(자식노드)를 가질 수 있는 자료 구조를 뜻한다!
Binary Heap(이진 힙)은 부모(P)와 자식(C)의 관계가 일정한 규칙((MAX)P >= C 이거나 (MIN)P <= C)을 만족하는 자료구조다.
Binary Search Tree(이진 탐색 트리)는 부모(P)와 2개의 왼쪽 자식(LC)/ 오른쪽 자식(RC)의 관계가 일정한 규칙
(P > LC && P < RC)을 만족하는 자료구조다.
위의 BST(이진 탐색 트리)에 추가적인 규칙을 세워 균형을 유지하는 자료구조를 Red-Black Tree(자가 균형 이진 탐색 트리)라고 한다!
- 모든 노드는 Red 또는 Black
- 루트 노드는 항상 Black
- 모든 잎 노드(끝 노드)는 Black
- Red 노드의 자식 노드는 모두 Black
(Red 노드가 연속적으로 나올 수 없음) - 어떤 노드에서 시작하여 리프 노드까지의 모든 경로에는 같은 수의 Black 노드가 포함됨
(이를 ‘Black-Height’라고 함)
위와 같은 규칙들을 통해 끝(루트 노드)과 끝(잎 노드)의 균형을 맞추어 한쪽 방향으로 편향 되지않은 이진 탐색트리를 구성할 수 있다!
Hash Table과 BST
Hash Table은 Key와 Value를 저장해두어 Key를 통해 저장된 Value에 접근할 수 있는 자료구조로, 이러한 자료 구조는 데이터 저장/삭제/검색 이 O(1)의 시간복잡도를 가져 매우 빠르나, 메모리 사용량이 상대적으로 크고 범위 검색이나 순차적 접근이 어렵다.
BST(이진탐색트리)는 데이터가 정렬된 상태로 유지되므로 범위 검색이나 순차적 접근이 가능하나 데이터 저장/삭제/검색에
평균 O(log n)의 시간복잡도를 가지고 있으며, 편향된 트리 구조의 경우 시간 복잡도가 O(n)까지 악화될 수 있다..
이러한 특징들로 인해 Hash Table은 빠른 검색에, BST는 범위 검색/정렬에 우위가 있다!