진강이의 성장일지

이진탐색트리(Binary Search Tree)의 개념이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이다.데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적으로 쓰인다.**(복습)- 이진트리 - 한 노드의 자식 노드가 최대 2개(왼쪽,오른쪽)인 트리- 포화 이진 트리 : 모든 레벨의 노드가 꽉 차있으며, 단말 노드를 제외한 모든 노드의 차수가 2인 이진 트리.- 완전 이진 트리 : 단말 노드들이 트리 왼쪽부터 채워진 형태의 이진 트리.- 높이 균형 트리 : 모든 단말 노드의 깊이 차이가 많아야 1인 이진 트리.- 완전 높이 균형 이진 트리 : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리.이진탐색트리의 정의이진탐색트리..

힙의 구현에 어울리는 것은? 연결리스트 아니라 배열앞서 우선순위 큐의 구현에 어울리는 것은 힙으로 결론이 났다.그렇다면 힙의 구현방법에 대해서 고민해보자. 힙은 트리이고 트리를 구현하는 방법에는 배열과 연결리스트가 있다. 이 둘 중 뭘 이용해야 할까? 정답은 배열이다.완전 이진 트리의 구조를 갖고 또 그 구조를 유지해야 하는 힙은 배열 기반으로 구현해야 한다. 연결리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않기 때문이다. 배열 기반 힙을 구현하려면?배열을 기반으로 투리를 구성하는 방법을 요약하자면 다음과 같다.노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열이 인덱스 값이 된다. 위 문장을 그림으로 설명하자면 다음과 같다...

우선순위 큐우선순위 큐는 이름처럼 '큐'와 관련이 있다. 앞서 공부한 큐의 핵심 연산 두 가지는 enqueue(큐에 데이터 삽입), dequeue(큐에 데이터 꺼내기)가 있었다. 마찬가지로 우선순위 큐의 핵심 연산도 enqueue(우선순위 큐에 데이터 삽입), dequeue(우선순위 큐에 데이터 꺼내기)이다. 하지만 큐와 우선순위는 연산의 결과에서 차이가 있는데, 큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산 결과는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. ** 우선순위 큐에서 중요한 것은 '우선순위'인데 그럼 우선 순위는 어떻게 결정 되는가? -> 프로그래머가 결정한다. 우선순위 큐의 구현 방법1. 배열을 기반으로 구현하는 방법2. 연결 리스트를 기반..