트리 (완전 이진, 포화 이진, Max-heap, Min-heap)

완전 이진 트리 (Complete binary tree)

root에서 레벨 순으로 (좌에서 우로 M)

leaf 노드를 제외한 모든 노드의 자식 수가 2개

포화 이진 트리 (Perfect binary tree)

레벨 I의 노드 수 : 2^(i - 1)

레벨 3의 노드 수 : 2^(3-1) = 4개

트리의 노드 수 : 2^3 - 1 = 7개

leaf 노드를 제외한 모든 노드의 자식 수가 2개

완전 이진 트리를 만족함

 

이진트리의 부모를 구하는 방법

⌊자식 노드/2⌋

ex) 5번째 노드의 부모는 몇 번째 노드인가?

⌊5/2⌋ ( 5/2 = 2.5 의 바닥함수는 2 ) : 2 번째 노드가 부모 노드

 

이진트리의 자식를 구하는 방법

부모 * 2, 부모 * 2 + 1

ex) 3번째 노드의 자식은 몇 번째 노드인가?

3 * 2와 3 * 2 + 1 : 6번째 노드와 7번째 노드가 자식 노드

Heap

배열로 구현하는 것이 표준

완전 이진 트리의 일종

최대값이나 최소값을 빠르게 찾아내도록 만들어졌다.

 

Max-heap (binary)

완전 이진 트리이다.

가장 큰 값이 뿌리가 된다.

(부모노드는 자식노드에 들어있는 값보다 크거나 같다)

 

Min-heap (binary)

완전 이진 트리이다.

가장 작은 값이 뿌리가 된다.

(부모노드는 자식노드에 들어있는 값보다 작거나 같다)

 

- 삽입 (Max-heap):

1. 마지막 노드 자리에 값을 삽입한다.

2. 부모와 값을 비교한다.

3. 부모보다 값이 크다면(작다면) 서로 위치를 바꾼다.

4. 2번과 3번을 부모가 없거나 더 큰(작은) 부모가 나올 때까지 반복한다.

 

ex) 2 3 5 1 7 6 을 가지고 max-heap을 만들어 보자

1.

2를 삽입해준다.

 

2.

3을 삽입한다.

부모노드인 2와 비교했을 때 3이 더 크기때문에 서로의 위치를 바꾸어준다.

 

3-1.

5를 삽입한다.

 

3-2. 

5를 삽입하고 5의 부모인 ⌊3/2⌋ ( (3번째 노드 / 2)의 바닥함수 )인 1번째 노드와 비교한다.

1번째 노드에는 3이 저장되어 있고 삽입된 수는 5이니 3과 5를 바꿔준다.

 

4.

1을 삽입하는데 가장 마지막 위치인 4번째 노드에 입력한다.

부모와 비교한다. 부모는 2이고 나는 1이므로 max-heap 조건을 만족한다.

 

5-1.

7을 가장 마지막 방인 5번째 노드에 삽입한다.

 

5-2.

7을 삽입한 뒤 부모노드와 비교한다.

부모 노드는 2이므로 7보다 작으니 위치를 바꿔준다.

 

5-3.

7이 2번째 노드에 저장되어 있는데 부모노드가 존재함으로 다시 한번 부모노드와 비교해준다.

부모노드는 5이므로 7보다 작으니 위치를 바꾸어 준다.

더이상 부모노드가 존재하지 않음으로 7의 입력을 마친다.

 

 

6-1.

6을 마지막 노드 자리인 6번째 노드에 저장해준다.

 

6-2.

부모노드인 3번째 노드(⌊6/2⌋)의 수와 비교해준다.

부모노드에는 3, 입력한 수는 6이므로 서로의 자리를 바꾸어준다.

 

6-3 부모노드인 1번째 노드(⌊3/2⌋)과 비교해준다.

부모노드에는 7, 입력한 수는 6임으로 자리가 맞음을 확인하고 삽입을 종료한다.

 

 

- 삽입 (Max-heap) (Ruby Code):

# frozen_string_literal: true
 
class MaxHeap
  def initialize
    @heap = []
  end
 
  def insert_node(value)
    # 마지막 노드 자리에 값 삽입
    @heap.push(value)
    p @heap
    # 부모와 값을 비교
    # 부모 => ((heap.length - 1) / 2)
    # 프로그래밍에서는 숫자가 0부터 시작함으로 -1을 해야 하지만
    # -1을 하고 시작하면 배열의 인덱스가 0 1 2 ... 이렇게 되는데 3번째 노드의 부모가
    # 1로 잡혀버린다.(2 / 2 = 1) 그래서 -1을 하는 대신 아래의 부모를 찾는 연산(25)에서
    # +1한 child를 이용해 부모를 찾고 그 값에 다시 -1을 하여 0부터 시작하는 인덱스에
    # 맞게 부모를 설정해준다.
    child = @heap.length - 1
    puts "child index: #{child}"
    # 입력한 수의 인덱스(child)가 1이상이라면 (부모 노드가 존재한다면 (2번째 노드부터))
    while child >= 1
      # 부모 노드는 child / 2의 몫
      # 위의 주석에서 나온 부모를 찾는 연산
      parent = ((child + 1) / 2) - 1
      puts "parent index: #{parent}"
      # 자식이 부모보다 크다면 교환한다.
      if @heap[child] > @heap[parent]
        temp = @heap[child]
        @heap[child] = @heap[parent]
        @heap[parent] = temp
        # 자식이 더 크다면 부모 위치로 가서 다시 부모를 탐색하도록 인덱스 전달
        child = parent
      else
        # 부모가 인덱스가 더 크다면 반복문을 빠져나가기 위해서 child에 0을 입력
        child = 0
      end
    end
  end
 
  def read_node
    print @heap
  end
end
 
heap = MaxHeap.new
heap.insert_node(2)
heap.insert_node(3)
heap.insert_node(5)
heap.insert_node(1)
heap.insert_node(7)
heap.insert_node(6)
heap.read_node
 

코드 결과

 

- 삭제: (뿌리 삭제)

1. 뿌리를 삭제한다.

2. 제일 마지막 노드를 뿌리 노드로 올린다.

3. 뿌리(1)의 자식( j 의 자식은 (jx2, jx2+1) )인 2, 3과 비교한다.

4. 셋 중 가장 큰(작은) 값이 뿌리에 위치하고 남은 자리에 위치한다.

5. 남은 자리에서도 자식들과 크기를 비교하는 작업을 반복한다. (자식이 없거나 자식들보다 클(작을) 때까지)

 

ex1) 7 5 6 1 2 3 을 가지는 max-heap에서 루트를 삭제해보자

1.

7을 삭제한다.

 

2.

제일 마지막 노드인(6번째 노드) 3을 7이 위치했던 1번째 노드로 옮긴다

 

3.

1번째 노드로 들어온 3과 자식 노드들 (1*2, 1*2+1)인 2번째 노드, 3번째 노드와 비교한다.

셋 중 가장 큰 값이 1번째 노드에 들어온다.

 

4.

자식 노드가 있는지 확인한다.

없음으로 노드 삭제를 완료한다.

 

 

 

ex2) 6 5 3 1 2 을 가지는 max-heap에서 루트를 삭제해보자

1.

6을 삭제한다.

 

2.

마지막 노드인 2를 1번째 노드로 가져온다.

 

3.

자식 노드 (2, 3번째 노드) 와 비교한다.

제일 큰 값인 5가 1번 노드에 위치한다.

 

4. 2번째 노드로 옮겨간 2와 자식 노드인 4, 5번째 노드를 비교한다.

5번 노드는 존재하지 않고 4번노드인 1은 2보다 작기 때문에 삭제를 완료한다.

 

 

- 삭제 (Max-heap) (Ruby Code):

# frozen_string_literal: true
 
class MaxHeap
  def initialize
    @heap = []
  end
 
  def insert_node(value)
    # 마지막 노드 자리에 값 삽입
    @heap.push(value)
    # 부모와 값을 비교
    # 부모 => ((heap.length - 1) / 2)
    # 프로그래밍에서는 숫자가 0부터 시작함으로 -1을 해야 하지만
    # -1을 하고 시작하면 배열의 인덱스가 0 1 2 ... 이렇게 되는데 3번째 노드의 부모가
    # 1로 잡혀버린다.(2 / 2 = 1) 그래서 -1을 하는 대신 아래의 부모를 찾는 연산(25)에서
    # +1한 child를 이용해 부모를 찾고 그 값에 다시 -1을 하여 0부터 시작하는 인덱스에
    # 맞게 부모를 설정해준다.
    child = @heap.length - 1
    # 입력한 수의 인덱스(child)가 1이상이라면 (부모 노드가 존재한다면 (2번째 노드부터))
    while child >= 1
      # 부모 노드는 child / 2의 몫
      # 위의 주석에서 나온 부모를 찾는 연산
      parent = ((child + 1) / 2) - 1
      # 자식이 부모보다 크다면 교환한다.
      if @heap[child] > @heap[parent]
        temp = @heap[child]
        @heap[child] = @heap[parent]
        @heap[parent] = temp
        # 자식이 더 크다면 부모 위치로 가서 다시 부모를 탐색하도록 인덱스 전달
        child = parent
      else
        # 부모가 인덱스가 더 크다면 반복문을 빠져나가기 위해서 child에 0을 입력
        child = 0
      end
    end
  end
 
  def delete_node
    # @heap[0] = nil
    # @heap[0] = @heap.pop
 
    # @heap.delete_at(0)
    # @heap.insert(0, @heap.pop)
 
    # 첫번째 요소(루트, 최대값(최소값))를 삭제한다.
    @heap.shift
    index = 0
    # 루트를 삭제하고 마지막 노드를 루트자리에 옮긴다
    @heap.unshift(@heap.pop)
    # 자식이 존재한다면 반복
    while @heap[((index + 1) * 2) - 1] != nil
      # 새로 생긴 루트와 자식 노드(j * 2, (j * 2) + 1)들을 비교한다.
      # 세개의 값 중 가장 큰 값이 루트 노드가 된다.
      # 배열은 0부터 시작하기 때문에 먼저 +1을 해서 자식을 구해주고
      # -1을 하여 배열의 연산에 맞게 변환해준다.
      child1 = ((index + 1) * 2) - 1
      child2 = ((index + 1) * 2)
      # 첫번째 자식은 존재하지만 두번째 자식은 존재하지 않거나
      # 첫번째 자식이 두번째 자식보다 크다면 첫번째 자식과 비교
      compare = if @heap[child2].nil? || @heap[child1] > @heap[child2]
                  child1
                else
                  child2
                end
      if @heap[index] < @heap[compare]
        temp = @heap[index]
        @heap[index] = @heap[compare]
        @heap[compare] = temp
        # 자식이 더 크다면 자식의 위치로 가서 다시 자식을 탐색
        index = compare
      else
        # 자식이 더 작거나 같다면 반복문을 빠져나가기 위해 index 값 변경
        index = @heap.length
      end
    end
  end
 
  def read_node
    p @heap
  end
end
 
heap = MaxHeap.new
heap.insert_node(2)
heap.insert_node(3)
heap.insert_node(5)
heap.insert_node(1)
heap.insert_node(7)
heap.insert_node(6)
heap.read_node
heap.delete_node
heap.read_node
heap.delete_node
heap.read_node
 

코드 결과