Computer Science/Data Structure 자료구조11 자료구조 힙(Heap) 알아보기 자료구조 힙(Heap) 알아보기 힙(Heap)은 무엇인가? 힙은 완전 이진 트리(Complete binary tree)의 한 종류이다. 완전 이진 트리에는 마지막 레벨을 제외하고는 빈 노드가 존재하지 않는다. 따라서 배열로 구현하기에 적합한 이진 트리이다. 루트 노드가 그 트리의 최댓값 혹은 최솟값을 가진다. 루트 노드가 트리의 최댓값을 가지면 최대 힙(Max heap) 루트 노드가 트리의 최솟값을 가지면 최소 힙(Min heap) 힙의 종류 최대 힙 (Max heap) 최대 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은 트리이다. 부모 노드의 Key 값 >= 자식 노드의 Key 값 루트 노드의 Key 값 = 트리의 최댓값 최소 힙 (Min heap) 최소 힙은 각 노드의 값이 자식 노드의 값보다.. 2020. 6. 14. 자료구조 이진 트리(Binary tree)의 순회(Traversal) 이진 트리의 순회 트리의 순회란? 트리의 모든 노드를 한 번씩 방문하는 것을 말한다. 트리 순회 방식은 노드를 방문하는 순서에 따라서 달라진다. 트리 순회에 필요한 용어 V - 노드를 방문 L - 왼쪽 서브 트리로 이동 R - 오른쪽 서브 트리로 이동 이진 트리의 순회 방법 전위 순회 (Preorder) 노드를 방문한다. 왼쪽 서브 트리로 이동한다. 오른쪽 서브 트리로 이동한다. 노드 A를 방문 노드 A의 왼쪽 서브 트리로 이동 -> 노드 B를 방문 노드 B의 왼쪽 서브 트리로 이동 -> 노드 D를 방문 노드 D는 단말 노드이기 때문에 서브 트리로 이동 불가 -> B로 돌아간다 -> B의 오른쪽 서브 트리로 이동-> 노드 E를 방문 노드 E는 단말 노드이기 때문에 서브 트리로 이동 불가 -> A로 돌아간.. 2020. 6. 13. 자료구조 이진 트리(Binary Tree)의 종류 Binary Tree 이진 트리 이진 트리(Binary Tree) 란 무엇인가? 각각의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다. 정렬과 검색 알고리즘을 위한 하나의 도구 이진 트리의 모양에 따라 알고리즘의 성능에 차이가 있다. 트리의 형태는 레벨과 노드 수에 따라서 결정된다. 이진 트리(Binary Tree) 의 종류 1. Perfect binary tree 포화 이진 트리 포화 이진 트리는 모든 레벨의 노드가 가득 차있는 트리이다. 노드가 2개의 자식을 가지고 있다. 차수(Degree) 가 2 이다. 모든 노드가 가득 차있어 단말 노드부터 루트노드까지의 높이가 같다. 노드의 개수 n = 2^h - 1, h 는 높이 A는 B 와 C를 자식으로 가져 꽉 차있고, B는 D 와 E, C는 F .. 2020. 6. 11. 자료구조 트리(Tree) 간단하게 알아보기 Data Structure Tree 자료구조 트리 트리(Tree) 란 무엇인가? 트리는 계층 구조(Hierarchical structure)로 이루어진 노드(Node)와 간선(Edge)의 집합이다. 부모-자식 관계의 계층 구조. 다음 노드는 여러 개가 될 수 있지만 이전 노드는 반드시 하나이다. 간선(Edge) 이란? 노드 사이를 연결하는 선이다. 부모-자식간의 관계를 나타내기 위해서 간선을 사용한다. 노드의 종류 트리에서 노드의 위치에 따라 구별되는 노드 루트(Root) 노드 - 트리의 첫번째 노드이다. 단말(leaf) 노드 - 자식 노드가 없는 노드이다. 내부(Internal) 노드 - 자식 노드가 있는 노드이다. 트리에서 노드 사이의 관계에 따라 구별되는 노드 부모(Parent) 노드 - 자식 노드.. 2020. 6. 9. 이전 1 2 3 다음
