Search for a command to run...
Articles tagged with #data-structures
B-tree와 B+tree B-tree란? : 이진트리를 확장한 자료구조 탐색 성능을 높이기 위해 평소에 데이터들의 높이를 균형있게 유지하는 Balanced Tree의 일종이다. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있다. 하나의 노드가 가질 수 있는 자식의 최대 숫자가 2보다 크다. 모든 단말(leaf) 노드는 같은 레벨에 있어야 한다. 항상 균형을 유지한다 (균형 잡힌 트리). 최대 M개의 자식을 가질 수 있는 B 트리를 M차...
우선순위 큐와 힙(Binary Heap) 우선순위 큐란? 데이터들이 우선순위를 가지고 있어, 우선순위가 높은 데이터부터 먼저 나가는 큐. 특정 순서대로 기다리고 있는 데이터들을 저장한다는 점에서 큐와 비슷하다.그러나 큐는 FIFO인 반면, 우선순위 큐는 PFO(Priority First Out)라는 점에서 차이가 있다. (PFO는 내가 만들어낸 단어다.) 우선순위 큐가 쓰이는 컴퓨터의 작업 스케줄링(운영체제 내용)에서는 우선순위에 따라 ...
Graph (그래프) 그래프란? 그래프 : 정점(vertex)과 간선(edge)으로 이뤄진 비선형 자료구조.현실 세계의 사물, 객체, 추상적인 개념 간의 연결 관계를 표현한 것 그래프는 정점(Vertex, node)과 간선(edge)으로 이뤄진 비선형 자료구조이며 정점과 간선들의 유한 집합이라고 할 수 있다.e.g. 도시들을 연결하는 도로망, 사람들의 지인 관계, 네트워크, 웹 사이트 간의 링크 관계 그래프에는 부모 자식 관계에 대한 제약이 ...
Tree (트리) 자료가 계층적인 구조를 가진다면 어떻게 할까?가계도, 모집합과 부분집합, 컴퓨터의 디렉토리 구조 등 계층적인 관계를 표현하려고 한다면 선형 자료구조(큐, 스택 )는 더 이상 적합하지 않다.트리는 이런 계층적인 구조를 표현할 때 적합하며, 원소들간에 일대다(one-to-many) 관계를 가진다.여기서 일대다라는건, 부모 노드쪽에선 다수의 자식 노드를 갖지만 자식 노드들은 오직 하나의 부모 노드를 갖는다는걸 의미. 트리는 자료...
Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. 스택, 큐, 데크는 모두 추상 자료형(ADT)이다. 즉, 언어에서 기본적으로 제공되는게 아니라 데이터와 연산들에 의해 정의되는 추상적인 자료구조이다. 각각을...