트리(이진트리 순회, 힙)

---

---

이진트리 순회

 

 

순회란 트리의 노드들을 체계적으로 방문하는 것이다.

이진트리에서의 순회는 전위순회(VLR), 중위순회(LVR), 후위순회(LRV) 총 3가지가 있다.

 

아래의 그래프로 3가지 순회 방법 예시를 들것이다.

전위 순회 ( V L R )

전위 순회란 부모노드를 먼저 탐색하고 왼쪽 자식, 오른쪽 자식 순으로 탐색하는 순회이다.

 

A -> B -> D -> H -> I -> E -> J -> C -> F -> G

 

중위 순회 ( L V R )

중위 순회란 왼쪽 자식노드를 먼저 탐색하고, 부모노드, 오른쪽 자식 노드 순으로 탐색하는 순회이다.

 

H -> D -> I -> B -> E -> J -> A -> F -> C -> G

 

후위 순회 ( L R V )

중위 순회란 오른쪽 자식노드를 먼저 탐색하고, 부모노드, 왼쪽 자식 노드 순으로 탐색하는 순회이다.

 

H -> I -> D -> J -> E -> B -> F -> G -> C -> A

 

---

힙

 

완전이진트리에 있는 노드중에서 키 값이 가장 큰 노드나 가장 작은노드를 쉽게 찾기 위해 만든 자료 구조

최대힙 예시

 

최대힙

• 키값의 최대값을 쉽게 찾기위해서 만들어진 자료 구조
• 부모노드의 키값 >= 자식노드의 키값
• 루트노드 : 키값이 가장 큰 노드

 

최소힙

• 키값의 최소값을 쉽게 찾기위해서 만들어진 자료 구조
• 부모노드의 키값 >= 자식노드의 키값
• 키값이 가장 작은 노드

 

힙의 활용

우선순위 큐를 구현하는데 가장 효율적인 방법이 힙 방법이다.

추가 / 삭제 O(lonN) , 최대값 / 최솟값 O(1)

완전정렬보다 관리 비용이 적음

---

힙의 연산

 

< 최대 힙 기준>

삽입

1. 삽입할 자리 확장
2. 확장할 자리에 삽입할 원소 저장
3. 만약 자신의 부모노드보다 저장된 원소가 크다면 부모노드와 삽입원소 교체
4. 부모노드보다 작거나 루트 노드가 되었을 때까지 교체

삭제

1. 루트노드의 원소값 삭제
2. 마지막 노드의 값 삭제후 루트노드에 저장
3. 만약 자신의 자식노드보다 저장된 원소가 작다면 자식노드와 현재 원소 교체
4. 자식노드보다 크거나 리프노드가 되었을때까지 교체

 

---

우선순위 큐

 

우선순위 큐란 우선순위를 가진 항목들을 저장 하는 큐이다. 일반 큐와는 다르게 원소들은 우선순위를 가지고 있으며 큐에 삽입 순서와 무관하게 우선순위에 따라 배출된다.

 

Java.util.PriorityQueue()

원소들의 natural ordering에 의해 기본 정렬

우선순위 큐 사용시 반드시 Comparator 재정의