반응형 Computer Science3 힙 트리(Heap Tree)란 무엇일까? 힙 트리(Heap Tree) 또는 힙(Heap)이란? 트리가 무엇인지 모른다면? '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻으로, 항상 완전 이진 트리의 형태 이진 트리란? 항상 부모의 값 > 자식(들)의 값 = Max heap 혹은 최대 힙 혹은 부모의 값 < 자식(들)의 값 = Min heap 혹은 최소 힙 루트노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장 ※ 최댓값(혹은 최솟값)을 O(1)O(1)안에 찾을 수 있음 사용하는 이유? 데이터들 중 가장 큰 값을 찾기 위해서 완전 이진 트리를 쓴다? X (최댓값(최솟값)을 O(1)O(1)안에 찾기 위해서) 삽입/삭제의 속도가 빠르기 때문에 쓴다? O 데이터 처리 데이터의 삽입, 삭제 모두 O(logN)이 소요된다. ※시간 복잡도O(l.. 2021. 11. 1. 이진 트리(Binary Tree)란 무엇일까? 이진 트리(Binary Tree) 트리가 무엇인지 모른다면? 부모 노드 밑의 자식 노드 개수(=차수, degree)를 최대 2개로 제한하는, 트리의 가장 간단한 형태다. 모든 트리는 이진 트리 형태로 재구성할 수 있기 때문에 특별한 이유가 없는 이상 트리는 보통 이진 트리로 구현된다. 일반적인 n개의 자식을 가질 수 있는 트리 구조이다. 각 노드의 첫번째 자식 노드 간선만 남기고 나머지 간선은 지운다. 형제 노드를 간선으로 연결한다. 이쁘게 정렬한다. Left-Child, Right-Sibling이라 부르는 이 방법으로 모든 트리를 이진 트리 형태로 재구성할 수 있다. 이진 트리의 종류 정 이진 트리(full binary tree) 모든 트리의 자식은 0개나 2개다. A의 자식 : (B, C) 2개 B의.. 2021. 10. 29. 트리(Tree)란 무엇일까? 트리(Tree) - 부모-자식 관계로 정의 - 부모에서 자식으로 간선이 이어져 있는 유향 그래프 (방향을 가진) 그래프이다. 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf node/leaf): 자식이 없는 노드. (단말 노드) 간선(edge): 부모 노드와 자식 노드를 연결하는 선 레벨(level): 루트 노드부터 노드까지 연결된 간선 수의 합 높이(height): 가장 긴 루트 경.. 2021. 10. 28. 이전 1 다음 반응형
