이진 탐색 트리

1. 이진 탐색 트리란?

🌟 정의

• 이진 트리와 이진 탐색 알고리즘이 결합된 자료구조.
• 데이터는 계층적으로 저장되며, 트리의 각 노드가 최대 두 개의 자식을 가짐.
• 각 노드의 왼쪽 서브트리 값은 현재 노드 값보다 작고, 오른쪽 서브트리 값은 현재 노드 값보다 큽니다.

---

1-1. 주요 특징

1. 정렬된 데이터:
   • 모든 노드의 왼쪽 서브트리 값은 해당 노드보다 작고, 오른쪽 서브트리 값은 해당 노드보다 큽니다.
2. 재귀적 정의:
   • 이진 탐색 트리는 각 서브트리(왼쪽, 오른쪽) 역시 이진 탐색 트리입니다.
3. 시간 복잡도:
   • 평균적으로 탐색, 삽입, 삭제의 시간 복잡도는 O(log N).
   • 단, 트리가 한쪽으로 치우친 경우 최악의 시간 복잡도는 O(N).

---

2. 이진 탐색 트리의 장단점

2-1. 장점

1. 탐색 효율:
   • 이진 탐색 알고리즘을 사용하여 빠르게 검색 가능.
2. 다양한 응용:
   • 데이터베이스, 컴파일러 심볼 테이블, 우선순위 큐 등의 구현에 사용.
3. 동적 크기 관리:
   • 정적 배열과 달리 크기에 제한이 없음.

---

2-2. 단점

1. 균형 문제:
   • 한쪽으로 치우치면 연결 리스트처럼 동작, 탐색 속도가 느려짐.
2. 구현의 복잡성:
   • 삽입, 삭제 시 균형을 유지해야 하는 경우가 많음.

---

3. 이진 탐색 트리의 구조

3-1. 노드 구조

struct Node {
    Node* parent = nullptr;
    Node* left = nullptr;
    Node* right = nullptr;
    int key = 0;
};

• parent: 부모 노드를 가리킴.
• left: 왼쪽 자식 노드를 가리킴.
• right: 오른쪽 자식 노드를 가리킴.
• key: 노드에 저장된 값.

---

3-2. 트리 클래스

class BinarySearchTree {
public:
    void Insert(int key);
    void Delete(int key);
    Node* Search(Node* node, int key);
    Node* Min(Node* node);
    Node* Max(Node* node);
    Node* Next(Node* node);
    void Replace(Node* u, Node* v);
private:
    Node* _root = nullptr;
};

• Insert: 새로운 값을 삽입.
• Delete: 특정 값을 삭제.
• Search: 특정 키를 검색.
• Min, Max: 최소값, 최대값 검색.
• Next: 특정 노드의 다음 노드(중위 순회 기준) 검색.
• Replace: 두 노드를 교체.

---

4. 주요 연산 구현

4-1. 삽입

새로운 값을 트리에 삽입합니다.

void BinarySearchTree::Insert(int key) {
    Node* newNode = new Node();
    newNode->key = key;

    if (_root == nullptr) {
        _root = newNode;
        return;
    }

    Node* node = _root;
    Node* parent = nullptr;

    while (node) {
        parent = node;
        if (key < node->key) {
            node = node->left;
        } else {
            node = node->right;
        }
    }

    newNode->parent = parent;
    if (key < parent->key) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
}

• 동작 과정:
  1. 새로운 노드를 생성.
  2. 트리를 탐색하여 삽입 위치를 결정.
  3. 부모 노드와 연결.

---

4-2. 검색

특정 키를 가진 노드를 검색합니다.

Node* BinarySearchTree::Search(Node* node, int key) {
    if (node == nullptr || key == node->key) {
        return node;
    }
    if (key < node->key) {
        return Search(node->left, key);
    } else {
        return Search(node->right, key);
    }
}

• 재귀 호출로 트리를 탐색하여 키 값이 일치하는 노드를 반환.

---

4-3. 최소값과 최대값

• 최소값: 왼쪽 자식을 따라 내려감.

Node* BinarySearchTree::Min(Node* node) {
    while (node->left) {
        node = node->left;
    }
    return node;
}

• 최대값: 오른쪽 자식을 따라 내려감.

Node* BinarySearchTree::Max(Node* node) {
    while (node->right) {
        node = node->right;
    }
    return node;
}

---

4-4. 다음 노드 (중위 순회 기준)

Node* BinarySearchTree::Next(Node* node) {
    if (node->right) {
        return Min(node->right);
    }
    Node* parent = node->parent;
    while (parent && node == parent->right) {
        node = parent;
        parent = parent->parent;
    }
    return parent;
}

• 오른쪽 자식이 있을 경우: 오른쪽 서브트리에서 가장 작은 값 반환.
• 오른쪽 자식이 없을 경우: 부모를 따라 올라가며 다음 값을 찾음.

---

4-5. 삭제

void BinarySearchTree::Delete(Node* node) {
    if (node == nullptr) return;

    if (node->left == nullptr) {
        Replace(node, node->right);
    } else if (node->right == nullptr) {
        Replace(node, node->left);
    } else {
        Node* next = Next(node);
        node->key = next->key;
        Delete(next);
    }
}

• 자식 노드가 하나일 경우: 자식을 부모와 연결.
• 자식 노드가 둘일 경우: 다음 노드를 찾아 대체한 뒤, 다음 노드를 삭제.

---

4-6. 노드 교체

void BinarySearchTree::Replace(Node* u, Node* v) {
    if (u->parent == nullptr) {
        _root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    if (v != nullptr) {
        v->parent = u->parent;
    }
}

• 부모 노드와 연결을 갱신하여 노드 u를 v로 대체.

---

5. 시간 복잡도

연산	평균 시간 복잡도	최악의 시간 복잡도
탐색	O(log N)	O(N)
삽입	O(log N)	O(N)
삭제	O(log N)	O(N)

• 최악의 경우는 트리가 한쪽으로 치우친 경우 발생.

---

6. 이진 탐색 트리와 이진 트리 비교

특징	이진 트리	이진 탐색 트리
정렬	데이터 정렬되지 않음	데이터가 정렬된 순서로 저장
탐색 효율성	O(N)	O(log N)
데이터 추가 규칙	없음	왼쪽: 작음, 오른쪽: 큼
용도	다양한 트리 기반 알고리즘 구현에 사용	데이터 저장 및 검색 용도로 사용

---

7. 이진 탐색 트리의 문제점

• 한쪽으로 치우친 경우, 탐색 성능이 선형 시간(O(N))으로 감소.
• 균형 트리(AVL 트리, Red-Black 트리)와 같은 구조가 필요.

---