[자료구조] 이진 탐색 트리, 힙

트리는 컴퓨터 구조에서 많이 사용하는 구조 입니다. 가장 대표적인 예로 파일 시스템이 있습니다.

이진트리는 다음과 같은 구조로 되어 있습니다.

하나의 노드는 자식노드를 최대 2개까지만 가질 수 있죠.

이진 탐색 트리는 이진 트리와 형태가 같으면서 한 가지 조건이 더 붙어 있습니다. 

바로 왼쪽 자식 노드는 부모 노드의 수보다가 작은 값을 가지고

오른쪽 노드는 부모 노드의 수 보다 큰 값을 가진다는 규칙 입니다.

위노드에서 그럼 중복된 숫자가 제거가 됩니다. 왜냐 하면 크거나 작지 않고 같은 값이기 때문에 위 규칙이 어긋나기 때문입니다.

그러면 조금 수정하면 위와 같은 형태가 되겠습니다.

제가 js로 구현한 코드는 아래와 같습니다..

이진 트리는 insert, delete, search  모두 Log(N)의 복잡도를 갖습니다.

힙은 최대힙과 최소힙이 있습니다. 이 자료구조도 이진트리의 형태를 갖습니다. 

이 자료구조는 참 재밌는 자료구조 입니다. 특정 영역에서 두곽을 나타내거든요. 예를들면 지금 러시아 월드컵이 한창인데

우리나라 선수를 최대 힙에 다 넣고, 수비에서 5명 꺼내오고, 공격에서 5명 꺼내오고, 미드필더에서 5명 꺼내오고 이러면

각 포지션에서 가장 잘하는 선수 5명씩 꺼내온 겁니다. 항상 가장 큰 값을 갖는 녀석을 루트로 두기 때문에 가능하죠.

힙은 다음과 같은 규칙을 따릅니다.

• 힙의 자료는 배열로 저장하며, 첫 번째 인데스(0인 인덱스)는 사용하지 않는다.
• leftChildNode index = parentNode inex * 2
• rightChildNode index = parentNode inex * 2 + 1
• parentNode index = childNode / 2 (나머지는 버림)

저는 js로 구현했고 최대힙과 최소힙을 생성하는 객체를 리턴하도록 구현했습니다.

class를 안쓰고 prototype을 연습하려고 만들었습니다. 코드가 좀 정리할 필요가 있겠지만,, 일단은 ㅎㅎ