트리 (Tree) 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조 노드들을 간선으로 연결한 계층형(Hierarchical) 자료구조 트리를 구성하고 있는 구성요소들(용어) Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다. Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다. Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다. Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다. 이진트리 (Binary Tree) 각 노드가 최대 두개의 자식을 갖..
"힙에서 할 수 있는건 어차피 균형 이진 트리에서도 할 수 있지 않나요? 그러면 균형 이진 트리가 더 제공해주는 기능이 많은데 힙을 쓸 이유가 있나요?" 라고 물었을 때 뭐라고 답을 하면 깔끔한 답이 될까요? 답은 이렇습니다. 힙에서 할 수 있는걸 균형 이진 트리에서 할 수 있는 것이 맞고, 자가 균형 트리라는 가정하에 시간복잡도가 O(lg N)O(lgN)으로 동일한 것도 맞습니다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현도 쉽고, 공간도 적게 차지하기에 최소 혹은 최댓값의 확인/삭제만 필요할 떄에는 힙을 쓰는 것이 더 좋습니다. 힙은 삽입, 최솟(혹은 최댓)값 삭제가 O(lg N), 최솟(혹은 최댓)값 확인이 O(1)입니다. 즉, 최소 최대값 확인은 힙이 더 유리하다. from htt..
Array 1. 물리적 저장순서와 논리적 저장순서가 일치한다. 2. 메모리상에 연속적으로 위치하므로, cache locality에 유리하다. 3. Index를 통해 해당 원소에 접근이 가능하다. 즉, Random Access가 가능하다. 4. 삽입, 삭제시 1번의 특징을 지키기위해 데이터들의 shifting이 필요하고, O(n)의 시간복잡도를 갖는다. 5. compile-time에 크기가 결정되고 메모리의 stack 영역에 할당된다. Linked List 1. 각 원소들이 다음 원소의 위치(주소)를 저장하고 있는 자료구조. 종류에 따라 이전 원소의 위치도 저장하고 있기도 함. 2. 다음원소의 주소를 저장하는 공간 즉, overhead가 존재 3. 메모상에 연속적으로 저장 되지 않는다. 4. 어떤 원소에 ..