이진 트리, 힙 트리

이진 트리는 부모가 최대 2개의 자식을 가지는 트리이다.

이런식의 구조를 가지고 있음!

 

이진 트리 중에 이진 검색 트리가 있는데

 

왼쪽에는 부모보다 작은것, 오른쪽에는 부모보다 큰 것이 존재함!

 

이러한 구조를 지니고 있어 검색에 용이하다! 32라는 값을 찾는다면? 크니까 오른쪽 

작으니까 왼쪽 이렇게 빠르게 찾을 수 있다. (이진탐색 알고리즘과 비슷한 것 같음)

 

하지만 하나의 문제점이 있는데, 이렇게 한줄로 할 경우에는 결국 이진 검색 트리의 이점을 잃고 리스트와 동일한 구조가 되어버리니까  삽입, 삭제가 일어날 때 트리를 재 배치한다고 한다!

 

이진 검색 트리와 비슷한 힙 트리라는 개념도 있는데

 

힙 트리는 이진 트리의 구조를 하고있으나 몇가지의 제약조건이 추가된 형태다.

 

제약조건중 첫 번째는 부모가 자식보다 무조건 커야 한다는 것이고

두 번째는 마지막(밑에)를 제외한 모든 레벨에 노드가 꽉 차있어야 한다는 것이고

데이터는 항상 왼쪽부터 들어간다는 것!

 

 

이러한 제약조건이 있어서 데이터의 개수를 알면 트리의 구조를 알 수 있다.

 

데이터를 6개 가지고 있는 힙 트리 구조이다.

 

그래서 배열을 이용해서 힙 구조를 표현할수도 있다고 한다.

 

i번째의 왼쪽 자식은 2 * i + 1이다. i번째의 오른쪽 자식은 2 * i + 2이다.

 

여기서 2를 곱해주는것은 이진트리이기 때문에 2를 곱해주는것이고 왼쪽은 한칸, 오른쪽은 두칸을 가기 때문에 그만큼 더하는것이다.

 

i번째의 부모는 (i - 1) / 2를 해주면 부모가 나옴! 

 

데이터를 추가한다면 규약을 지키기 위해서 부모와 비교를 하면서 크다면 타고 타고 올라가는 모습을 볼 수 있음

 

최대값을 꺼내는것은 root가 결국 최댓값이기 때문에 root를 빼면 됨. 하지만 root를 빼면 구조가 이상해지므로 정리를 해 주어야 하는데, root 제외한 모든 노드는 결국 원 위치에 있다. 따라서 마지막으로 온 애를 root로 변경하고 다시 비교를 하면서 구조를 잡는다.