Chapter 15. 이진 탐색 트리로 속도 향상

Chapter 15. 이진 탐색 트리로 속도 향상

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 트리
2. 이진 탬색 트리
        2-1. 검색
        2-2. 삽입
        2-3. 삭제
3. 이진 탐색 트리 다뤄보기
4. 이진 탐색 트리 순회

• 이진 탐색 트리는 순서를 유지하면서도 빠른 검색, 삽입, 그리고 삭제가 가능한 자료 구조이다.

1. 트리

• 트리(tree)는 노드를 기반으로한 자료 구조이다.
  
  • 단, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다는 차이가 있다.
• 트리 용어 정리
  • 루트(root) : 트리의 최상위 노드
  • 부모(parent) : 노드의 바로 상위 노드. (노드가 속한 노드).
  • 자식 : 노드의 바로 하위 노드.
  • 자손(descendant) : 노드에 속하는 모든 하위 노드. (자식 노드를 포함한다).
  • 조상(ancestor) : 노드가 속하는 모든 상위 노드. (부모 노드를 포함한다).
  • 레벨(level) : 트리에서 같은 줄(row)를 의미한다. (트리의 같은 층).
  • 프로퍼티(property) : 트리의 균형잡힌 정도
    • 모든 노드의 하위 노드의 수가 같다면 균형(balanced) 트리이다.
    • 적어도 하나의 노드가 갖는 노드의 수가 다르다면 불균형(imbalanced) 트리이다.

---

2. 이진 탐색 트리

• 트리에 이진(binary)과 탐색(search)이라는 수식어가 붙는다.
  • 이진 트리 : 각 노드의 자식이 0개, 1개 혹은 2개인 트리이다.
  • 이진 탐색 트리
    • 이진 트리를 기반으로 한다.
    • 각 노드의 자식은 최대 왼쪽에 하나, 오른쪽에 하나이다.
    • 한 노드의 왼쪽 자손은 해당 노드보다 작은 값만 포함한다.
    • 한 노드의 오른쪽 자손은 해당 노드보다 큰 값만을 포함한다.
• 하나의 트리 노드 구현

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.value = val
        self.leftChild = left
        self.rightChild = right
        
# 테스트------------------------------------------------
node1 = TreeNode(25) # val = 25, left = None, right = None
node2 = TreeNode(75) # val = 75, left = None, right = None
root = TreeNode(50, node1, node2) # 50, node1 = 25, node2 = 75

 

 

2-1. 검색

• 검색 알고리즘 수행
  • step 1 : 노드를 '현재 노드'로 지정한다.
    • 알고리즘 시작 시에는 루트 노드가 현재 노드이다.
  • step 2 : 현재 노드의 값을 확인한다.
    • 찾고 있는 값이라면 종료한다.
  • step 3
    • 찾고 있는 값 < 현재 노드 : 왼쪽 하위 트리를 검색한다.
    • 찾고 있는 값 > 현재 노드 : 오른쪽 하위 트리를 검색한다.
  • step 4 : 찾고 있는 값을 찾거나, 트리 바닥에 닿을 때까지(트리에 값이 없는 경우) 'step 1 ~ step 3'을 반복한다.

 

이진 탐색 트리 검색의 효율성

• 이진 탐색 트리 검색의 빅 오는 $O(logN)$ 이다.
  • 이유는 각 단계마다 절반씩 노드가 제외되기 때문이다. (노드의 수가 1, 2, 4, 8, ... 으로 존재한다).
  • 단, 포화 균형 이진 탐색 트리인 경우에만 해당한다.
• 이진 탐색 트리에 N 개의 노드가 존재한다면, 트리의 레벨 수는 약 $logN$이 된다. (직접 여러 개의 트리를 그려보면 패턴을 알 수 있다).
• 정렬된 배열의 이진 검색 효율성 또한 $O(logN)$으로 이진 탐색 트리와 동일하다.
  • 단, 삽입의 경우 이진 탐색 트리가 더 많은 이점을 갖는다.
• 코드 구현
  • 트리는 루트 노드부터 점점 깊이 들어간다.
  • 점점 깊이 들어가는 구조이기에 재귀를 활용하기 좋다.
  • 재귀의 경우 이해가 안된다면 스택 구조를 직접 종이에 써가며 이해하면 비교적 쉽게 이해할 수 있다.
  • self를 사용하지 않기에 class 내부 메서드가 아닌 개별 함수로 정의된다.

def search(searchValue, node):
    # 기저 조건: 노드가 없거나
    # 찾고 있던 값이면
    if node is None or node.value == searchValue:
        	return node
    
    # 찾고 있는 값이 현재 노드보다 작으면
    # 왼쪽 자식을 검색한다.
    elif searchValue < node.value:
        return search(searchValue, node.leftChild)
    
    # 찾고 있는 값이 현재 노드보다 크면
    # 오른쪽 자식을 검색한다.
    else: # searchValue > node.value
        return search(searchValue, node.rightChild)

•  

 

 

2-2. 삽입

• 이진 탐색 트리는 삽입에서 가장 뛰어나다.
• 이진 탐색 트리 삽입은 $logN + 1$ 단계가 필요하다.
  • $logN$ : 삽입될 위치의 노드까지 검색하는 단계
  • $1$ : 검색 완료 후 삽입하는 단계
• 배열의 경우 삽입 시에 시프트가 포함되기에 빅 오는 $O(N)$이 된다. 즉, 이진 탐색 트리보다 비효율적이다.
• 요약하면 이진 탐색 트리는 검색과 삽입이 모두 $O(logN)$로 효율적이다.
  • 따라서 데이터를 자주 변경하는 애플리케이션에 적합하다.
• 단, 주의할 점은 무작위로 정렬된(그러니까 정렬되지 않은) 데이터로 트리를 형성해야 한다.
  • 정렬된 데이터로 트리를 형성할 경우 일자 트리가 형성된다. 따라서 선형 검색(O(N))과 차이가 없다.
  • 무작위로 정렬된 데이터의 경우 일반적으로 균형 트리가 형성되기에 검색에 O(logN)이 된다. 즉, 삽입도 $O(logN)$이 된다.
• 코드 구현
  • self를 사용하지 않기에 class 내부 메서드가 아닌 개별 함수로 정의된다.

def insert(value, node):
    # 삽입 값이 노드 값보다 작은 경우
    if value < node.value:
        
        # 왼쪽 자식이 없으면 왼쪽 자식으로서 값을 삽입한다.
        if node.leftChild is None:
            node.leftChild = TreeNode(value)
        else:
            insert(value, node.leftChild)
    
    # 삽입 값이 노드 값보다 큰 경우
    elif value > node.value:
        
        # 오른쪽 자식이 없으면 오른쪽 자식으로서 값을 삽입한다.
        if node.rightChild is None:
            node.rightChild = TreeNode(value)
        else:
            insert(value, node.rightChild)

 

 

2-3. 삭제

• 요약 정리
  • 자식 노드가 없는 경우 : 그냥 삭제한다.
  • 자식 노드가 하나인 경우 : 대상 노드를 삭제하고, 삭제된 자리를 자식 노드로 대체한다.
  • 자식 노드가 둘인 경우 : 대상 노드를 삭제하고, 삭제된 자리를 후속자 노드로 대체한다.
    • 후속자 노드 : 삭제된 노드보다 큰 값 중 최솟값.
    • 후속자 노드를 찾는 법
      • step 1 : 삭제된 노드의 바로 오른쪽 자식으로 내려간다.
      • step 2 : step 1에서 내려간 오른쪽 자식의 왼쪽 자식을 따라 바닥(bottom)까지 내려간다.
      • step 3 : 도착한 바닥 노드가 후속자 노드이다.
    • 만약 후속자 노드에도 오른쪽 자식이 있다면, 후속자 노드의 부모 노드의 왼쪽 자식으로 넣는다.
• 일반적으로 이진 탐색 트리의 삭제의 빅 오는 $O(logN)$ 이다.
  • 배열은 삭제 후 빈 공간을 메워야 하기에 시프트가 포함된다.
  • 이진 탐색 트리는 연결이 끊긴 자식 노드와 연결하는 단계가 포함된다.
• 코드 구현
  • 책의 설명을 보는 것도 좋지만 코드를 읽고서 이해하는 것이 더 쉬울 수도 있다.
  • 재귀 알고리즘이 이해가 안되어 있는 경우 이해하기 어려울 수 있다. 재귀는 스택으로 직접 손으로 써서 풀어보면 비교적 쉽다.
  • self를 사용하지 않기에 class 내부 메서드가 아니라 개별 함수로 사용된다.

def delete(valueToDelete, node): # valueToDelete : 삭제하려는 값, node : 트리의 루트
    
    # 트리 바닥에 도달해서 부모 노드에 자식이 없으면 기저 조건이다.
    if node is None:
        return None
    
    # 삭제하려는 값이 현재 노드보다 작거나 크면
    # 현재 노드의 왼쪽 혹은 오른쪽 하위 트리에 대한 재귀 호출의 반환값을
    # 각각 왼쪽 혹은 오른쪽 자식에 할당한다.
    elif valueToDelete < node.value:
        node.leftChild = delete(valueToDelete, node.leftChild)
        
        # 현재 노드(와 존재한다면 그 하위트리)를 반환해서
        # 현재 노드의 부모의 왼쪽 혹은 오른쪽 자식의 새로운 값으로 쓰이게 한다.
        return node
    elif valueToDelete > node.value:
        node.rightChild = delete(valueToDelete, node.rightChild)
        return node
    
    # 현재 노드가 삭제하려는 노드인 경우
    elif valueToDelete == node.value:
        
        # 현제 노드에 왼쪽 자식이 없으면
        # 오른쪽 자식(과 존재한다면 그 하위 트리)을
        # 그 부모의 새 하위 트리로 반환함으로써 현재 노드를 삭제한다.
        if node.leftChild is None:
            return node.rightChild
        
            # (현재 노드에 왼쪽 또는 오른쪽 자식이 없으면
            # 이 함수 코드 첫 줄에 따라 None을 반환하게 된다.)
        
        elif node.rightChild is None:
            return node.leftChild
        
        # 현재 노드에 자식이 둘이면
        # 현재 노드의 값을 후속자 노드의 값으로 바꾸는
        # (아래) lift 함수를 호출함으로써 현재 노드를 삭제한다.
        else:
            node.rightChild = lift(node.rightChild, node)
            return node
        
def lift(node, nodeToDelete):
    
    # 이 함수의 현재 노드에 왼쪽 자식이 있으면
    # 왼쪽 하위 트리로 계속해서 내려가도록 함수를 재귀적으로 호출함으로써
    # 후속자 노드를 찾는다.
    if node.leftChild:
        node.leftChild = lift(node.leftChild, nodeToDelete)
        return node
    # 현재 노드에 왼쪽 자식이 없으면
    # 이 함수의 현재 노드가 후속자 노드라는 뜻이므로
    # 현재 노드의 값을 삭제하려는 노드의 새로운 값으로 할당한다.
    else:
        nodeToDelete.value = node.value
        # 후속자 노드의 오른쪽 자식이 부모의 왼쪽 자식으로 쓰일 수 있도록 반환한다.
        return node.rightChild

---

3. 이진 탐색 트리 다뤄보기

• 이진 탐색 트리는 검색, 삽입, 그리고 삭제 모두 일반적으로 $O(logN)$이 걸린다.
• 정렬된 배열은 검색이 이진 탐색 트리만큼 빠르지만 삽입과 삭제는 그렇지 못하다.
  • 자주 값을 변경해야하는 애플리케이션이라면 이진 탐색 트리를 자료 구조로 사용할 수 있다.
  • 데이터 변경 빈도가 낮고 조회가 주 작업이라면 정렬된 배열을 사용할 수 있다.

---

4. 이진 탐색 트리 순회

• 이진 탐색 트리로 정렬된 전체 책 리스트 알파벳 순으로 출력
  • 자료 구조에서 모든 노드를 방문하는 과정을 자료 구조 순회(traversal)이라 부른다.
  • 리스트를 순서대로 출력할 수 있도록 트리를 알파벳 오름차순으로 순회할 수 있어야 한다.
    • 교재에서는 중위 순회(inorder traversal) 사용.
• 트리 순회 수행
  • step 1 : 노드의 왼쪽 지식에 함수(traverse)를 재귀적으로 호출한다.
    • 더이상 왼쪽 자식이 없는 노드에 닿을 때까지 호출한다.
  • step 2 : 해당 노드의 값을 출력한다.
  • step 3 : 노드의 오른쪽 자식에 함수(traverse)를 재귀적으로 호출한다.
    • 더이상 오른쪽 자식이 없는 노드에 닿을 때까지 호출한다.
• 코드
  • 내용이 복잡하기에 설명을 생략한다. 교재에 있는 스택 설명을 쫒아가면 이해할 수 있다.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.value = val
        self.leftChild = left
        self.rightChild = right
        
# 순회--------------------------------------------------------------------
    def traverse_and_print(node):
        # 노드가 비어있는 경우 None을 반환한다.
        if node is None:
            return
    
        # 우선 노드의 좌측 자식부터 재귀를 수행한다.
        traverse_and_print(node.leftChild)
    
        # 중간에 print()가 있는 이유는
        # 우측 자식 노드를 확인하기 전 해당 노드를 먼저 출력해야하기 때문이다.
        # (우측 자식 노드가 해당 노드보다 크기 때문에 정렬을 위해서)
        print(node.value)
    
        # 중심 노드를 반환하고 우측 자식 노드에 재귀를 적용한다.
        traverse_and_print(node.rightChild)