이진트리 [ 힙 ]

이진트리 ( binary tree ) 는 부모 노드는 최대 2개의 자식노드를 가질수 있는 자료구조이다.

완전 이진 트리 모양이면서 힙성질을 따르면 힙 트리라고 한다.

 

1. 완전 이진 트리란?

마지막 레벨을 제외하고 자식 노드가 왼쪽부터 채워져 있는 트리를 일컫는다.

완전이진트리

2. 힙성질 만족?

부모노드의 키값이 자식노드의 키값이 작지 않은 경우 즉 부모노드의 키값이 자식노드의 키값보다 크거나 같은 경우에 힙성질을 만족한다.

힙성질 만족하지 않는 경우

위의 예시는 힙성질을 만족할까? 그렇지 않다. 루트노드부터 봐도 두 자식노드보다 키값이 작기 때문에 힙성질을 만족한다고 볼수 없다. 루트 노드 뿐만 아니라 level 2 의 두개 노드 ( 9, 6 ) level 3 (1 노드) 도 만족 하지 않는다. 같은 키값으로 힙성질을 만족하도록 재배치 해보자.

힙성질을 만족하는 경우

위의 예시는 힙트리를 만족하는 경우이다.

힙트리 특징

1. 상수시간 계산으로 부모노드의 왼쪽 자식노드 오른쪽 자식노드를 알수 있다.

- 루트노드 왼쪽 자식노드의 인덱스 = 1 (루트노드 인덱스) x 2 = 2

- 루트노드 오른쪽 자식노드의 인덱스 = 1 (루트노드 인덱스) x 2 + 1 = 3

- k 노드의 왼쪽 자식노드의 인덱스 = k x 2

- k 노드의 오른쪽 자식노드의 인덱스 = (k x 2) + 1

 

2. 상수시간 계산으로 자식의 부모 노드를 알수 있다. ( 정수나눗셈 )

- 루트노드 인덱스 = 2 (루트 왼쪽 자식 노드) // 2 = 1

- 루트노드 인덱스 = 3 (루트 오른족 자식 노드) // 2 = 1

- k 노드의 인덱스 = ( k 의 왼쪽 자식노드 인덱스 ) // 2

- k 노드의 인덱스 = ( k 의 오른쪽 자식노드 인덱스 ) // 2

 

3. 루트노드에는 항상 가장 큰 값이 들어있다.

 

Reference

한국외대, 컴퓨터전자시스템공학부, 자료구조 2020-1

https://www.youtube.com/watch?v=8XnPN6IB22Y