[Python] 트리 - 전위, 중위, 후위순회와 이진탐색트리

https://thinking-developer.tistory.com/74(참고)

트리

전위 순회(Preorder)

(1) 정의 및 순서

• 순회 순서: (현재 노드) → (왼쪽 서브트리) → (오른쪽 서브트리)
• 즉, 노드를 방문하자마자 그 노드의 정보를 처리(예: 출력)한 후, 왼쪽→오른쪽 순으로 내려갑니다.

(2) 특징

• 루트(root)를 가장 먼저 방문하므로, 트리 구조를 (부모-자식) 순서대로 파악하기 쉽습니다.
• 예를 들어, 트리를 복원하거나 계층적인 구조를 직관적으로 출력할 때 유용합니다.

중위 순회(Inorder)

(1) 정의 및 순서

• 순회 순서: (왼쪽 서브트리) → (현재 노드) → (오른쪽 서브트리)
• 왼쪽 서브트리를 모두 방문한 뒤, 현재 노드를 방문하고, 그 다음 오른쪽을 방문합니다.

(2) 특징

• 이진 탐색 트리(BST)에서 중위 순회를 하면, 노드 값이 오름차순(또는 내림차순)으로 정렬된 순서로 나열됩니다.
• 숫자/문자 같은 자료를 정렬된 형태로 얻어야 할 때 자주 사용됩니다.

후위 순회(postorder)

(1) 정의 및 순서

• 순회 순서: (왼쪽 서브트리) → (오른쪽 서브트리) → (현재 노드)
• 자식 노드를 모두 처리한 후에, 마지막에 부모 노드를 방문합니다.

(2) 특징

• 하위 노드(자식)들을 먼저 모두 처리한 뒤, 부모(상위) 노드를 처리해야 하는 경우에 유리합니다.
• 예를 들어, 노드 삭제, 서브트리 연산(병합 등)이 끝난 후 부모를 처리해야 하는 상황에 적합합니다.
• 트리 형태로 표현된 수식(Expression Tree) 을 계산할 때 자주 쓰이기도 합니다. (왼쪽/오른쪽 자식을 먼저 처리한 뒤에 연산자(부모)를 계산)

이진탐색트리(Binary Search Tree)

기본 조건

• 왼쪽 자식 노드의 키값은 자신 키값보다 작아야함
• 오른쪽 자식 노드의 키값은 자신 키값보다 커야함

장점

• O(log n)의 평균 시간복잡도를 가짐(탐색, 삽입, 삭제)
• 중위 순회를 통해 오름차순으로 값을 얻을 수 있음
• 노드를 삽입하기 용이함

단점

• 정렬된 상태로 값이 들어올 경우, 트리가 한쪽으로 기울어져서 성능이 O(n)으로 저하될 수 있음
  • 해소하기 위해 AVL, 레드-블랙 트리 같은 균형 이진 검색 트리를 활용함

트리의 흐름

1. 현재 노드의 key와 비교 : 입력이 현재 노드의 key보다 작으면 왼쪽, 크면 오른쪽으로 이동
2. 1을 반복하며 원하는 위치(key가 있는 노드, 또는 삽입할 자리)를 탐색

검색은 key를 찾으면 노드 반환, 없으면 None 반환

삽입은 적절한 삽입 빈 자리를 찾으면, 새 노드를 생성하여 연결

노드 삽입 구현

• 재귀

class Node:
    def __init__(self, key, value, left: Node = None, right: Node = None):
        self.key = key
        self.value = value # 선택적
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None  # 트리의 루트 노드


        def insert(node, key):
            # 기저 사례: 빈 자리(노드가 None)면 새 노드를 생성하여 반환
            if node is None:
                return Node(key)
            if key == node.key: # 중복키 삽입 실패
                    return False

            # 새 key가 작으면 왼쪽, 크면 오른쪽으로 재귀 호출
            if key < node.key:
                node.left = insert(node.left, key, value)
            else:
                node.right = insert(node.right, key, value)

            return node


# 사용 예시
root = None
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
    root = insert(root, val)

• 반복

class Node:
    def __init__(self, key, value, left: Node = None, right: Node = None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

def iterative_insert(root, key, value):
    new_node = Node(key, value)   # 새 노드 생성, value는 선택적

    if root is None: # 트리가 비어 있으면 새 노드가 루트가 됨
        return new_node

    current = root
    while True:
            if key == current.key: # 중복키 삽입 실패
                    return False

        if key < current.key:
            if current.left is None: # 새 값이 현재 노드보다 작으면 왼쪽 서브트리로 이동
                current.left = new_node # 빈 자리를 찾으면 새 노드를 연결하고 종료
                break
            else:
                current = current.left
        else:
            if current.right is None:# 새 값이 현재 노드보다 크거나 같으면 오른쪽 서브트리로 이동
                current.right = new_node
                break
            else:
                current = current.right

    return root  # 루트는 변경되지 않으므로 그대로 반환

# 사용 예시:
if __name__ == "__main__":
    values = [50, 30, 70, 20, 40, 60, 80]
    root = None
    for val in values:
        # 매번 삽입 후 루트를 갱신 (초기에는 root가 None이므로 새 노드가 루트가 됨)
        root = iterative_insert(root, val)

탐색 구현

1. 루트에 주목
2. 주목하고있는 노드의 key값이 None일 경우, 검색을 실패하고 종료
3. 아닐경우, target(찾는 값)과 key를 비교
   1. target = key : 검색 종료
   2. target > key : 우측 자식 노드로 이동
   3. target < key : 왼쪽 자식 노드로 이동
4. 2번 과정으로 반복

• 재귀

def search_recursive(node, key):
    # 기저 사례: 노드가 없거나, 찾은 경우
    if node is None or node.key == key:
        return node # None일 경우 감지하여 none 그대로 반환함
    # key가 현재 노드보다 작으면 왼쪽 서브트리에서 검색
    if key < node.key:
        return search_recursive(node.left, key)
    # key가 크면 오른쪽 서브트리에서 검색
    return search_recursive(node.right, key)

• 반복

def search_iterative(root, key):
    current = root  # 현재 탐색 위치를 나타내는 변수
    while current is not None and current.key != key:
        # key 비교에 따라 왼쪽 또는 오른쪽으로 이동
        if key < current.key:
            current = current.left
        else:
            current = current.right
    return current