이진 탐색 트리 편집하기

'''이진 탐색 트리'''(Binary Search Tree, BST)는 이진 트리의 한 유형으로, 모든 노드가 다음과 같은 '''이진 탐색 속성'''을 만족하는 트리 구조이다.
*왼쪽 서브트리의 모든 노드는 부모 노드보다 작다.
*오른쪽 서브트리의 모든 노드는 부모 노드보다 크다.
*각 서브트리 또한 이진 탐색 트리이다.
이진 탐색 트리는 탐색, 삽입, 삭제 연산을 평균적으로 O(log N)에 수행할 수 있어, 정렬된 데이터를 효율적으로 관리하는 데 사용된다.
==특징==
*각 노드의 최대 자식 노드 수는 2개이다.
*중복된 값은 허용되지 않는 경우가 일반적이다.
*정렬된 데이터를 효과적으로 탐색할 수 있다.
*트리의 균형 상태에 따라 성능이 결정된다.
**균형 잡힌 경우: O(log N)
**편향된 경우: O(N) (한쪽으로 치우친 리스트 형태)
==기본 연산==
이진 탐색 트리는 다음과 같은 연산을 수행할 수 있다.
===탐색(Search)===
*루트에서 시작하여 원하는 값을 찾을 때까지 왼쪽 또는 오른쪽으로 이동.
*찾고자 하는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동.
===삽입(Insertion)===
*새로운 노드를 추가할 위치를 찾은 후, 적절한 위치에 삽입.
===삭제(Deletion)===
삭제할 노드의 경우에 따라 다르게 처리됨:
*자식이 없는 노드 → 단순히 제거.
*자식이 하나인 노드 → 부모 노드와 직접 연결.
*자식이 두 개인 노드 → 오른쪽 서브트리에서 가장 작은 값(후계자)을 찾아 대체.
==예제==
다음과 같은 BST를 고려하자.
       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13
*탐색(6) → 8에서 왼쪽(3), 다시 오른쪽(6)으로 이동하여 찾음.
*삽입(5) → 6의 왼쪽(4)에서 오른쪽(5)에 추가.
*삭제(3) → 후계자(4)로 대체.
==코드 예제==
<syntaxhighlight lang="python">
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = Node(value)
            return
        self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:
            if node.left:
                self._insert(node.left, value)
            else:
                node.left = Node(value)
        else:
            if node.right:
                self._insert(node.right, value)
            else:
                node.right = Node(value)

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, node, value):
        if not node or node.value == value:
            return node
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)

# 예제 실행
bst = BST()
for num in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(num)

print(bst.search(6).value)  # 출력: 6
</syntaxhighlight>
 출력 결과 예시:
 6
==응용==
이진 탐색 트리는 다양한 분야에서 활용된다.
*'''데이터베이스''' → 인덱싱 구조
*'''운영체제''' → 메모리 관리, 파일 시스템
*'''네트워크''' → 라우팅 테이블 최적화
*'''인공지능''' → 의사결정 트리(Decision Tree)
==같이 보기==
*[[트리 이론]]
*[[AVL 트리]]
*[[레드-블랙 트리]]
*[[B-트리]]
==참고 문헌==
*Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
*Knuth, Donald E. "The Art of Computer Programming, Volume 3: Sorting and Searching." Addison-Wesley, 1998.
[[분류:알고리즘]]
[[분류:트리 이론]]