트리(Tree)와 힙(Heap)

트리란?

비 선형 자료구조의 일종으로 스택과 큐처럼 이어져 있는 것이 아니라, 서로간의 노드와 간선으로만 이루어져 있는 형태이다.

트리 예시 자료

트리 순회 방법

• 중위 순회 : 왼쪽 자식, 자신, 오른쪽 자식 순으로 순회하는 방법이다.
• 전위 순회 : 자신, 왼쪽 자식, 오른쪽 자식 순으로 순회하는 방법이다.
• 후위 순회 : 왼쪽 자식, 오른쪽 자식, 자신 순으로 순회하는 방법이다.
• 레벨 순회 : 층을 한칸씩 내려가면서 순회하는 방식이다. BFS방식으로 쓰인다.

힙이란?

트리 중에서 완전 이진 트리로, 부모 노드보다 항상 작으면 MaxHeap, 부모 노드보다 항상 크면 MinHeap으로 표현할 수 있다.

힙의 특징은 넣을 때마다 자동으로 정렬되는 성질을 가지고 있으며 그 시간복잡도는 O(Nlogn)을 가지고 있다.

Java에서의 힙은 Priority Queue로 구현이 가능하며 아래에 관련 함수들을 적어두겠다.

 

• add : 우선순위 큐에 데이터를 삽입한다.
• offer : add와 같은 기능이지만 해당 데이터를 반환한다.
• poll : 첫 번째 값을 빼서 해당 데이터를 반환한다.
• peek : 첫 번째 값을 빼지 않고 값만 리턴한다.
• remove : poll과 같은 기능이지만 값이 비어있으면 예외를 발생시킨다.
• clear : 해당 큐를 전부 비운다.