dvpzeekke

Binary Heap(이진 힙)은 Complete Binary Tree 형식의 자료구조입니다. Complete Binary Tree는 배열에 기반하고 있기 때문에 random access가 가능합니다. Complete Binary Tree에 대한 설명은 아래 게시물을 참고해주세요. http://dvpzeekke.tistory.com/m/45 BST(Binary Search Tree, 이진 탐색 트리) BST(Binary Search Tree, 이진 탐색 트리) BST(Binary Search Tree, 이진 탐색 트리)는 이진 탐색 알고리즘을 트리에 적용한 자료구조입니다. 이진 탐색 트리의 정의는 다음과 같습니다. - 노드에 저장된 Key(키).. dvpzeekke.tistory.com Heap에는 Ma..

BST(Binary Search Tree, 이진 탐색 트리) BST(Binary Search Tree, 이진 탐색 트리)는 이진 탐색 알고리즘을 트리에 적용한 자료구조입니다. 이진 탐색 트리의 정의는 다음과 같습니다. - 노드에 저장된 Key(키)는 유일하다. - 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. - 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. - 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리의 탐색 연산은 O(log n)의 time complexity를 갖습니다. 이진 탐색 트리의 높이는 log (n + 1)이기 때문입니다. 하지만 이진 탐색 트리가 한 쪽으로 편향되어 있다면(Skewed Tree, 편향 트리) ti..

Tree(트리) Tree(트리)는 Hierarchical Relationship(계층적 관계)를 표현하는 자료구조입니다. 트리를 구성하는 구성 요소들은 다음과 같습니다. - Node(노드) : 트리를 구성하는 각각의 요소 - Edge(간선) : 노드와 노드를 연결하는 선 - Root Node(루트 노드) : 트리의 최상위 노드 - Terminal Node( = leaf Node, 단말 노드) : 트리의 최하위 노드 - Internal Node(내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드(루트 노드 포함) - Sub-Tree(서브 트리) : 루트 노드를 제거한 후 남아있는 부분 트리 - Degree of Node(노드의 차수) : 특정 노드에 연결된 서브 트리의 수 - Level(레벨) :..

List(리스트)는 동일한 자료형으로 된 원소들의 모임으로 linear list(선형 리스트)와 linked list(연결 리스트)로 나뉩니다. Linear list의 종류로는 배열, 스택, 큐, 순환 큐 등이 있습니다. Stack(스택) stack은 linear list의 일종으로, LIFO(Last-In, First-Out) 특징을 가집니다. 즉, 나중에 들어간 원소가 먼저 나오고, 먼저 들어간 원소가 나중에 나옵니다. 선반에 접시를 차곡차곡 쌓는 것을 연상하시면 됩니다. 접시를 하나 쌓을 때 stack의 가장 위 접시에 쌓고, 접시를 하나 집을 때, stack의 가장 위 접시를 집는 상황과 일치합니다. Queue(큐) queue는 linear list의 일종으로, FIFO(First-In, Firs..

List(리스트)는 동일한 자료형으로 된 원소들의 모임으로 linear list(선형 리스트)와 linked list(연결 리스트)로 나뉩니다. linear list의 종류로는 배열, 스택, 큐, 순환 큐 등이 있습니다. 이번 포스팅에서는 배열과 연결 리스트의 차이에 대해 설명합니다. Array(배열) Array(배열)은 가장 많이 사용되는 자료구조 중의 하나로 자료형이 동일한 원소들의 유한집합으로 정의됩니다. array에 속한 각 원소들은 메모리에 연속적으로 저장되어 논리적 저장 순서와 물리적 저장 순서가 일치합니다. 따라서 고유의 index를 통하여 random access가 가능합니다. 따라서 찾고자 하는 index의 값을 알고 있으면 O(1)에 해당 원소로 접근이 가능합니다. 하지만 삭제 혹은 삽..