본문 바로가기

공부한 내용/자료구조

Tree, Graph란 min-heap은 완전이진트리(complete binary tree)의 일종이라고 했습니다. 그렇다면 트리란 무엇일까요? Tree(트리) 트리란 노드로 이루어진 자료구조로, 하나의 루트 노드(node)를 가지고 있습니다. 루트 노드는 0개 이상의 자식 노드를 가지고 있습니다. 그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 자식 노드 역시 0개 이상의 자식 노드를 가지고 있고... 위 그림처럼 부모와 자식의 개념, 즉 계층구조를 가지고 있습니다. 그리고 배열이나 리스트와 다르게 하나의 자료 뒤에 여러 자료가 존재할 수 있는데, 이를 비선형(nonlinear) 자료구조라고 합니다. 각 노드는 어떤 자료형으로도 표현할 수 있습니다. 트리와 관련된 용어는 다음과 같습니다. 루트 노드(root nod.. 공부한 내용/자료구조 2022. 2. 23.
min-heap이란 이벤트루프에 대해 알아보던 중, setTimeout과 같은 함수들은 Timer phase의 min-heap에 타이머를 저장했다가, 이벤트루프가 Timer phase에 진입하게 되면 min-heap을 탐색하면서 시간이 경과된 타이머의 콜백을 실행한다는 것을 보게 되었습니다. min-heap이란? 완전이진트리(complete binary tree)의 일종으로, 최솟값을 빠르게 찾아내기 위한 자료구조입니다. min-heap은 부모노드의 키 값이 자식 노드의 키 값보다 작습니다. 반대로 부모노드의 값이 더 큰 max-heap도 있습니다. 힙에 무언가를 삽입할 땐, 다음의 과정을 거칩니다. 1. 맨 마지막 노드에 데이터를 추가 2. 부모 노드와 값을 비교하여, 부모가 더 크다면 부모 노드와 자식 노드의 위치를 교.. 공부한 내용/자료구조 2022. 2. 23.
queue와 stack 어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 합니다. queue(큐) 큐는 선입선출(FIFO, First In First Out)의 특성을 가지는 자료구조입니다. Javascript에서는 배열을 사용해서 간단하게 큐를 구현할 수 있습니다. class Queue { constructor() { this._arr = []; } enqueue(item) { this._arr.push(item); } dequeue() { return this._arr.shift(); } } const queue = new Queue(); queue.enqueue(1); queue.enq.. 공부한 내용/자료구조 2022. 2. 23.

티스토리툴바