datastructure8 자료구조 힙(Heap) 알아보기 자료구조 힙(Heap) 알아보기 힙(Heap)은 무엇인가? 힙은 완전 이진 트리(Complete binary tree)의 한 종류이다. 완전 이진 트리에는 마지막 레벨을 제외하고는 빈 노드가 존재하지 않는다. 따라서 배열로 구현하기에 적합한 이진 트리이다. 루트 노드가 그 트리의 최댓값 혹은 최솟값을 가진다. 루트 노드가 트리의 최댓값을 가지면 최대 힙(Max heap) 루트 노드가 트리의 최솟값을 가지면 최소 힙(Min heap) 힙의 종류 최대 힙 (Max heap) 최대 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은 트리이다. 부모 노드의 Key 값 >= 자식 노드의 Key 값 루트 노드의 Key 값 = 트리의 최댓값 최소 힙 (Min heap) 최소 힙은 각 노드의 값이 자식 노드의 값보다.. 2020. 6. 14. 자료구조 트리(Tree) 간단하게 알아보기 Data Structure Tree 자료구조 트리 트리(Tree) 란 무엇인가? 트리는 계층 구조(Hierarchical structure)로 이루어진 노드(Node)와 간선(Edge)의 집합이다. 부모-자식 관계의 계층 구조. 다음 노드는 여러 개가 될 수 있지만 이전 노드는 반드시 하나이다. 간선(Edge) 이란? 노드 사이를 연결하는 선이다. 부모-자식간의 관계를 나타내기 위해서 간선을 사용한다. 노드의 종류 트리에서 노드의 위치에 따라 구별되는 노드 루트(Root) 노드 - 트리의 첫번째 노드이다. 단말(leaf) 노드 - 자식 노드가 없는 노드이다. 내부(Internal) 노드 - 자식 노드가 있는 노드이다. 트리에서 노드 사이의 관계에 따라 구별되는 노드 부모(Parent) 노드 - 자식 노드.. 2020. 6. 9. [C언어] Array Stack 배열 스택 구현 스택이란 ? 리스트와 같이 선형 (Sequential) 구조 자료를 순차적으로 저장한다. 리스트와 다르게 LIFO(후입 선출) 자료의 추가와 제거가 TOP에서 이루어 진다. 스택에 필요한 주요 Operations Pop - 스택의 Top에 있는 자료를 제거한 후 반환한다. Push - 스택의 Top에 자료를 추가한다. Peek - 스택의 Top에 있는 자료를 반환한다. (제거 x) isEmpty - 스택이 비어있는지 확인한다. 배열 스택의 장점 속도가 빠르다 더 빨리 노드에 접근할 수 있다. 배열 스택의 단점 미리 저장할 데이터의 개수를 예측하고 여유롭게 스택의 크기를 지정해야한다. 나중에 데이터를 추가하기 위해서이다. 만약 데이터의 개수만큼 배열의 크기가 정해지면 나중에 새로운 데이터를 추가할 수 없게.. 2020. 6. 8. [C++] Doubly Linked List 이중 연결 리스트 구현 Doubly Linked List 이중 연결 리스트 구현 Doubly Linked List 는 무엇일까? Singly Linked List (단순 연결 리스트) 는 노드 사이의 연결이 단방향 이다. 하지만 Doubly Linked List (이중 연결 리스트)는 노드 사이의 연결이 양방향이다. 각각의 노드는 다음 노드에 대한 연결뿐만 아니라 이전 노드에 대한 연결도 가지고 있다. 그렇기 때문에 Doubly Linked List는 이전 노드, 다음 노드로의 접근이 모두 가능하다. Doubly Linked List의 노드 구조 Doubly Linked List의 구조 첫번째 노드는 이전 노드가 없기 때문에 이전 노드에 대한 링크는 NULL 이다. 또한, 마지막 노드는 다음 노드가 없기 때문에 다음 노드에 대.. 2020. 6. 8. 이전 1 2 다음
