TIL - 이진 트리 검색 (BST)

문제

- 이진 검색 트리에서 값을 검색합니다.
- BST 특징: 왼쪽 자식 < 부모 < 오른쪽 자식
- 이 특성을 이용하여 빠른 검색이 가능합니다.
- 왼쪽 서브트리의 모든 값 < 현재 노드 값
- 오른쪽 서브트리의 모든 값 > 현재 노드 값

 

[알고리즘] 트리 구조와 사용하는 이유, 이진 검색 트리

 

 

 

문제풀이

def search_bst(root, target):
    """
    BST에서 값 검색
    
    Args:
        root: 트리 루트
        target: 찾을 값
    
    Returns:
        True/False
    """
    if root is None:
        return False

    if root.value == target:
        return True
    if root.value > target:
        return search_bst(root.left, target)
    if root.value < target:
        return search_bst(root.right, target)

 

target 을 기준으로 현재 노드가 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리에서 검색하였다.

 

 

 

어려웠던 점

1. 이 문제도 재귀의 반환이 어려웠다. 
   • 디버깅 찍어보면서 어떤 흐름으로 갔는지 이해해보려고 노력했다.
   • 아직 머릿속에서 재귀함수가 추상적인 개념인 것 같다.