Tree (2)

순회 ≠ 탐색

순회는 노드 아래 쪽의 서브 트리만 돌지만, 탐색은 원칙적으로 전부 다 돌아야 한다.

 

• 수식 트리

수식을 표현하는 이진 트리

수식 이진 트리라고 부르기도 한다.

연산자는 루트 노드거나 가지 노드이고 피연산자는 모두 잎 노드이다!

 

수식 트리를

중위 순회하면 수식을 중위 표기법으로 쓰게 된다.

후위 순회, 전위 순회하면 각각 후위 표기법, 전위 표기법으로 쓰게 된다.

 

• 이진 탐색 트리

탐색작업을 효율적으로 하기 위한 자료구조

모든 원소는 서로 다른 유일한 키를 갖는다.

왼쪽 서브트리의 key < 루트 노드의 key < 오른쪽 서브트리의 key

왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.

 

중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

루트 노드를 중심으로 왼쪽은 루트보다 값이 작고 오른쪽은 루트보다 값이 크다.

 

• 이진 탐색 트리 - 연산

루트에서 시작할 때 탐색할 키 값을 루트 노드의 키 값과 비교한다.

키 값이 루트 노드의 키 값과 같으면 원하는 원소를 찾았으므로 탐색연산이 성공한다.

키 값 < 루트 노드의 키 값 : 루트 노드의 왼쪽 서브트리에서 탐색 연산을 수행

키 값 > 루트 노드의 키 값 : 루트 노드의 오른쪽 서브트리에서 탐색 연산을 수행

 

노드를 삽입하는 경우 (삽입 연산)

1. 먼저 탐색 연산을 수행한다.

→ 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 확인

→ 탐색 실패가 결정되는 위치가 삽입할 위치가 된다.

2. 탐색 실패한 위치에 원소를 삽입한다.

 

• 이진 탐색 트리의 성능

탐색, 삽입, 삭제 시간은 트리의 높이만큼 시간이 걸린다.

→ O(h) , h = 이진 탐색 트리(BST)의 깊이

 

평균의 경우 (이진 트리가 균형적으로 생성되어 있는 경우)

→ O(log n)

 

최악의 경우 (한쪽으로 치우친 경사 이진 트리의 경우)

→ O(n) , 순차 탐색과 시간복잡도가 같다.

 

• 힙 (Heap)

완전 이진 트리로 구현된 자료구조로서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기에 적합하다.

힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있다.

 

최대 힙 (max heap)

→ 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리

부모 노드의 키 값 > 자식 노드의 키 값 (형제 끼리는 상관없음)

루트 노드의 키 값이 가장 크다.

 

최소 힙 (min heap)

→ 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리

부모 노드의 키 값 < 자식 노드의 키 값

루트 노드의 키 값이 가장 작다.

 

완전 이진 트리가 아니거나 키 값의 대소 관계가 일정하지 않으면 힙이 아니다!

 

• 힙 연산 - 삭제

힙에서는 루트 노드의 원소만을 삭제할 수 있다.

루트 노드의 원소를 삭제하여 반환

힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.

# 최대힙
def enq(n):
    global last
    last += 1
    # 마지막 노드 추가 (완전이진트리를 유지하기 위해)
    h[last] = n     # 마지막 노드에 데이터 삽입
    # 부모 > 자식 조건을 만족하도록 유지해야 함
    # 비교를 위해 부모 노드 번호를 계산
    c = last
    p = c//2
    while p >= 1 and h[p] < h[c]:   # 부모가 있는데, 더 작으면
        h[p], h[c] = h[c], h[p]     # 교환
        c = p
        p = c//2

def deq():
    global last
    tmp = h[1]   # 루트의 키값 보관
    h[1] = h[last]
    last -= 1
    p = 1       # 새로 옮긴 루트
    c = p * 2
    while c <= last:    # 자식이 있으면
        if c+1 <= last and h[c] < h[c+1]:   # 오른쪽 자식이 있고 더 크면
            c += 1
        if h[p] < h[c]:
            h[p], h[c] = h[c], h[p]
            p = c
            c = p * 2
        else:
            break
    return tmp

N = 10  # 필요한 노드 수
h = [0]*(N+1)   # 최대 힙
last = 0    # 힙의 마지막 노드 번호
enq(2)
enq(5)
enq(3)
enq(6)
enq(4)

while last > 0:
    print(deq())

# 6
# 5
# 4
# 3
# 2

 

• 이진 탐색 트리 사용 이유

→ 시간 복잡도를 logN으로 줄일 수 있어서? (X 효율적이게 되는건 맞지만 정확한 답은 아니다.)

→ 이진탐색과 비교시, 시간 복잡도는 logN으로 동일한데 배열에 저장해 놓고 정렬해서 쓰지 않고 이진 탐색 트리를 왜 쓰는가?

이진 탐색 트리는 정렬 비용을 최소화해 효율적인 탐색 가능하기 때문!

 

기존의 이진탐색은 한가지를 간과했다. 정렬비용을 생각하지 않고 탐색만 고려한 것

list에서 삽입 ,삭제가 이루어지지 않아도 추가 정렬할 필요가 없다면 이진탐색만 해도 ㄱㅊ

그러나 현실에서는 데이터 추가 삽입, 삭제가 계속 일어나는 곳에서 탐색(검색) 필요

이진탐색은 항상 정렬된 상태가 유지 되어야 함. 이 때 ‘정렬비용’ 추가 발생

(이진 탐색 트리를 사용하는 이유)

 

• 정렬 비용 : 연속적인 데이터의 앞 쪽에서 데이터 삽입/삭제시 발생 ( 시간 복잡도 O(n))

정렬된 상태를 유지하려면 or 중간에 new 데이터(새로운 인덱스) 삽입 하려면, 삽입점 뒤의 자료들은 모두 한 칸씩 옮겨야 한다. 맨 앞에 추가된다면 모든 데이터 n개의 인덱스 수정 n번 발생.

 

lst = [1, 2, 3] 값은 연속적인 메모리 공간에 저장

lst = [1, 2, 3] 의 인덱스는 lst 내의 값들을 가르키는 ‘주소’ 이므로 연속적 공간에 저장되지 않음

lst에 100을 추가한다면 연속적인 공간에 1, 2, 3 다음에 100을 저장.

 

• 정렬 비용의 시간복잡도

list에서 데이터 갯수만큼 비례하여 시간 비용 발생하므로 데이터 삽입/삭제의 시간복잡도 O(n)

Tree에서는 트리의 높이만큼 시간 비용 발생 (logN)

 

이진 탐색 트리의 성능을 살펴보자

 

• 편향 이진트리

이진 트리에서 균형을 이루는 것이 왜 필요할까?

→ 좌우 노드의 갯수가 최대한 균형을 이루어야 잘 분할 되어있는 것이므로 권장됨

= 트리의 높이를 최소화

= 시간복잡도 최소화

 

어떤 값을 반복하며 검색하는 상황에서 부모를 기준으로

왼쪽으로 탐색하면 작은 값으로

오른쪽으로 탐색하면 큰 값으로

따라가며 탐색 하게 된다!

→ 가장 멀리 떨어진 값으로 따라가더라도 트리 높이만큼 반복을 수행한다.

(편향 이진 트리가 좋지 않은 이유)

 

편향 이진 트리가 길어진다면 그냥 list 에서 삽입/삭제/탐색이 이루어지는 것과 다를 게 없다.

 

• 검색 알고리즘

이진 탐색 트리 , 해싱

두가지를 현실에서 가장 많이 사용한다.

 

• 힙

완전 이진 트리에서 새로운 데이터의 삽입/삭제가 일어나는 와중에 max value, min value 알고 싶을 때 사용한다.

 

• 이진힙(binary heap)

구현이 가장 간단하여 이해하기가 용이하다.

 

단 2가지 유의점이 있다. (중요)

1) 완전 이진 트리 구조 유지

• 새로운 데이터 추가/삭제 과정 중에 완전 이진 트리 구조를 유지해야 함(1차 배열)
  → 1차 배열 형태로 저장

idx 1번 ~ N번 까지 중간에 빈 값 없이 모든 값 저장을 보장
데이터가 추가되어 N+1 개가 되더라도 N+1개 저장됨
→ 데이터 삭제한다면 끝을 가르키는 last는 N → N-1로 수정

• hsize : 맨 마지막 값이자 전체 자리수 나타내는 변수(stack의 top 같은 개념)
  • 루트 값을 어딘가 저장해 백업
  • 마지막 노드의 값을 루트 자리에 이동
  • 마지막 N 가르키던 hsize N-1 가르키도록 처리

 

2) 부모 - 자식 관계

트리 내에서 어떤 노드든지 부모 - 자식 관계 유지할 것

최대힙 : 부모>자식

최소힙 : 부모<자식 인 관계를 유지해야 함.

→ 충족되지 않는다면 서로 자리를 바꾼다.

 

1)번 먼저 처리 후 2)번을 처리한다.

 

# 최대힙
# 힙의 저장소 (H[0]은 사용하지 않음)
H = [0] * 100
hsize = 0  # 마지막 노드 번호(idx)이자 전체 노드 수 의미

# 최대힙 연산 종류: push, pop
# 힙은 공통적으로 관례적으로 쓰이는 이름 없지만 스택과 비슷하여 push, pop 을 주로 사용

def push(item):
    global hsize
    '''1. 완전 이진 트리 구조 유지'''
    hsize += 1  # 마지막 위치
    H[hsize] = item

    '''2. 부모 - 자식 관계 조정'''
    # hsize 바꾸면 안되니 부모 자식 가르키는 새로운 변수 p, c
    p, c = hsize // 2, hsize

    '''종료조건 1. 부모가 자식보다 큰 경우 2. 자식이 루트가 되는 경우'''
    # 반복 해나간다. 더이상 부모<->자식 바꿀 필요 없을 때 까지 또는 바꿀 것이 없을 때 까지
    while p > 0 and H[p] < H[c]:
        H[p], H[c] = H[c], [p]
        p, c = p // 2, p

def pop():
    # 설명 생략 알아서 해봐라
    pass

from heapq import heappop, heappush
data = [69, 10, 30, 2, 16, 8, 31, 22]

# 힙저장소를 리스트로 제공
H = []

for val in data:
    heappush(H, val)

while H:
    print(heappop(H))

# 2
# 8
# 10
# 16
# 22
# 30
# 31
# 69

다른 방법도 있다!

from queue import PriorityQueue
data = [69, 10, 30, 2, 16, 8, 31, 22]

Q = PriorityQueue()
for val in data:
    Q.put(val)

while not Q.empty():  # 그냥 Q: 이렇게 하면 안된다. empty 를 사용해야 함
    print(Q.get())

# 2
# 8
# 10
# 16
# 22
# 30
# 31
# 69

객체 지향적이라 heapq 보다 좀 더 쓰기가 편하다. 대신 처리시간이 좀 걸리는 방법이다.