Binary Search Tree (BST): 정렬된 이진 트리

Binary Search Tree, BST, 이진 탐색 트리, binary-search-tree

정의

Binary Search Tree (BST) 는 각 노드가 다음을 만족하는 이진 트리입니다.

• 왼쪽 서브트리의 모든 키 < 노드 키
• 오른쪽 서브트리의 모든 키 > 노드 키

연산: 탐색, 삽입, 삭제 모두 평균 O(log N). 최악은 O(N) (편향 트리).

연산

struct Node { int key; Node *l, *r; };

Node* search(Node* r, int k) {
    if (!r || r->key == k) return r;
    return k < r->key ? search(r->l, k) : search(r->r, k);
}

Node* insert(Node* r, int k) {
    if (!r) return new Node{k, nullptr, nullptr};
    if (k < r->key) r->l = insert(r->l, k);
    else if (k > r->key) r->r = insert(r->r, k);
    return r;
}

중위 순회 (inorder) 로 방문하면 키가 정렬된 순서로 출력됩니다.

왜 균형이 필요한가

정렬된 입력을 순서대로 삽입하면 일자 트리 가 되어 O(N) 로 퇴화합니다.

균형 유지 자료구조:

• AVL Tree: 엄격한 균형 (높이 차 <= 1)
• Red-Black Tree: 완화된 균형 (색 기반)
• Treap: 우선순위 무작위화
• Splay Tree: 접근 시 회전
• Order Statistics Tree: BST + 서브트리 크기

참고

• 관련 Segment Tree (구간 쿼리)
• 관련 BBST (균형 트리)
• 관련 Fenwick Tree (prefix sum)