완전이진트리 - 힙
힙(이진힙)힙은 완전이진트리의 한 종류로최대값 기준으로 정렬된 최대힙과 최솟값 기준으로 정렬된 최소힙이 있다.최대힙은 부모노드가 항상 자식노드 보다 값이 크며 루트 노드에 최대값이 매핑되어있다.최소힙은 부모노드가 항상 자식노드 보다 값이 작으며 루트 노드에 최솟값이 매핑되어있다.정렬기준에 따른 첫번째 값이 루트 노드에 존재하여 우선순위 조회 탐색시에 사용된다.자바에서 우선순위 큐에 사용된 자료구조 또한 힙이다. [힙의 특징]완전 이진트리부모노드의 키값과 자식노드의 키값 사이에는 대소관계 성립키값 대소관계는 오로지 부모자식 간에 성립되며 형제 사이에는 대소관계가 없음 heapify힙이 규칙을 지키고 균형을 유지하기 위해 사용되는 연산이 heapify이다. 최대힙에서 heapify 연산이 어떻게 수행되는지 ..
비선형 자료구조 - 트리
트리트리란 노드와 간선으로 이루어진 자료구조로 부모노드에서 자식노드로 향하는 계층 구조를 이루고 있다.그래프의 한 종류이지만 트리는 사이클이 존재하지 않고 노드간 연결 경로는 부모에서 자식으로 오직 하나 뿐이라는 특징이 있다.트리에는 이진트리, 이진탐색트리, 완전이진트리가 존재한다. 선형구조로는 계층 구조를 사용하지 못하기에 트리라는 자료구조를 사용한다.대표적인 사용사례가 DB의 인덱스 페이지이다.책의 목차와 같은 계층 구조를 통해 데이터의 빠른 접근을 보장한다. 트리의 정의하나의 루트 노드가 반드시 존재루트 노드를 제외한 모든 노드는 부모노드를 갖음모든 노드는 0개 이상의 자식 노드를 가질 수 있음사이클이 존재하지 않음노드의 갯수가 N이면, 간선의 수는 N-1트리는 방향그래프? 무방향 그래프?그래프 이..