02/10(4) - DFS

DFS - 깊이우선 탐색 : 루트노드에서부터 시작하여, 한방향으로 갈 수 있는데 까지 쭈~욱 내려가고 , 마지막을 만나면 마지막에 만난 갈림길로 가서 다른방향의 노드로 !!! 

 

각 노드에서 탐색하는 방법이 동일함 ( 재귀 이용 가능 ) 

-> 한 노드에 대해 내가 가지고 있는 좌자식 노드와, 우자식 노드만 탐색함 

 

[순회]

-전위순회 : 부모 - 좌 - 우

-중위순회 : 좌 - 부모 - 우

-후위순회 : 좌 - 우 - 부모

 

[ 힙 ] 

완전이진트리의 구조에서 이루어짐 ,, 빠르게 탐색이 가능 

최대힙 : 루트노드가 가진 값이 키값 최대 , 부모노드 > 자식노드 유지 

최소힙 : 루트노드가 가진 값이 키값 최소, 부모노드 < 자식노드 유지 

 

< 값 삽입 > 

완전 이진트리에서 마지막 인덱스 값 바로 뒤에 삽입한 후, 각 부모 노드와 비교해가며 SWAP -> 제자리 찾기 

: 층별로만 이동하면 되기 때문에 O(nlogn)

<루트 노드값 삭제 > 

가장 마지막 인덱스의 값으로 루트 대체 -> 자식 노드와 비교해가며 제자리 찾기 

: 층별로 이동하기 때문에 마찬가지로 O(nlogn)

< 단순 최대 / 최소 조회 > 

O (1)

---> 최대 또는 최소힙이므로, 힙정렬 가능 ( 일반 정렬보다 훨씬 빠름 ) 

 

java.util.PriorityQueue() : 각 원소 내에서 원소들 스스로 타원소와 비교해야함 , comparable 인터페이스 구현 필요 

java.util.PriorityQueue(Comparator comparator) : 매개변수의 comparator 가 알아서 비교도우미 역할 해줌 , 

 즉 , comparable 별도 구현 필요 없음 

 

PriorityQueue<Integer> pque = new PriorityQueue<>() // 이런식으로 하면, 원소들 스스로 comparable 인터페이스를 구현해서 비교해야 하는데, 원소인 Integer 내부로 들어가보면 comparable 을 구현하고 있음 

- > 별도의 액션 취하지 않아도 스스로 오름 차순으로 정렬해서 큐에 삽입해줌 !! 대박