🔍이진 탐색 트리(BST, Binary Search Tree)

이진 트리의 특수한 형태로, 이진 탐색이 효율적으로 동작할 수 있도록 고안된 자료구조의 일종. 정렬된 이진 트리

🧭이진 탐색 트리의 특징

• 왼쪽 서브트리에는 부모 노드보다 작은 값이 위치
• 오른쪽 서브트리에는 부모 노드보다 큰 값이 위치
• 중복된 키를 허용 하지 않는다.

📊이진 탐색 트리의 시간 복잡도

👉탐색/삽입/삭제

• 평균 : O(log n) → 트리가 균형 잡힌 상태일 때
• 최악 : O(n) → 트리가 한쪽으로 치우친 경우(사실상 연결 리스트)

---

✅이진 탐색 트리의 검색

1. 루트 노드부터 방문 하여 탐색을 진행
2. 검색 값이 루트보다 작으면 왼쪽으로, 크다면 오른쪽을 방문
3. 일치하는 값을 찾을때까지 절차 반복
4. 검색 값이 없으면 null 반환

---

✅이진 탐색 트리의 생성

50, 15, 62, 80, 7, 54, 11 의 요소로 이진트리를 생성한다고 했을때 과정은 다음과 같다.
1. 50을 트리의 루트에 삽입한다.
2. 다음 요소를 읽고 루트 노드 요소보다 작으면 왼쪽 하위 트리의 루트로 삽입
3. 루트 노드의 요소보다 크면 오른쪽 하위 트리의 루트로 삽입

---

✅이진 탐색 트리의 삽입

1. 루트에서 시작
2. 삽입 값을 루트와 비교하여 루트보다 작으면 왼쪽, 크다면 오른쪽
3. 리프 노드에 도달 한 후, 노드보다 크면 오른쪽, 작다면 왼쪽에 삽입

---

✅이진 탐색 트리의 삭제

1. 삭제할 노드가 리프 노드인 경우

바로 삭제

---

2. 삭제할 노드에 자식이 하나만 있는 경우

노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결

---

3. 삭제할 노드에 자식이 둘 있는 경우

자식이 둘 있는 경우 successor 노드를 찾는 과정이 추가된다.
successor 노드란 오른쪽 서브트리의 최소값을 말한다.
1. 삭제할 노드를 찾는다.
2. 삭제할 노드의 successor 노드를 찾는다
3. 삭제할 노드와 successor 노드의 값을 바꾼다
4. 노드를 삭제한다.

---

BST는 한쪽으로 치우치면 성능이 O(n)이라는 단점이 있는데, 이런 단점을 해결하기 위해 나온 균형 이진 탐색 트리 중 대표적인 트리로 AVL 트리와 레드-블랙 트리(RBT)가 있다. 이것도 같이 알아보자.

💡AVL 트리 (Adelson-Velsky and Landis Tree)

• 최초로 제안된 자기 균형 이진 탐색 트리로, 말단 노드의 레벨 차이가 항상 1이하로 나는 트리이다.
• 노드 삽입/삭제 후 자동으로 균형을 유지하기 위해 회전 연산을 사용하며, 회전 연산은 트리의 구조를 변경하여 균형을 복구한다.
• AVL 트리는 탐색/삽입/삭제 연산의 시간 복잡도가 모두 O(log n)이다.
• 균형을 유지하기 위해 회전 연산이 필요하므로 이진 탐색 트리보다는 조금 구현이 복잡하다.
• 자주 변경되는 데이터 셋에 적합하며 데이터의 삽입과 삭제가 빈번한 경우에도 항상 빠른 탐색 속도를 제공한다.

---

💡레드-블랙 트리(Red-Black Tree, RBT)

• 모든 노드는 Red / Black의 색을 가져야한다.
• 루트 노드는 항상 블랙이다.
• NIL 노드는 항상 블랙이다.(value가 없는 말단 노드를 항상 가진다. NIL은 Null Leaf를 뜻함)
• 레드 노드의 자식 노드는 항상 블랙이다.
• 각 노드에서 말단 노드로 가는 블랙 노드의 수는 항상 같아야 한다.

👉 위 다섯가지 규칙을 만족하는 트리가 레드-블랙 트리이다.

• 레드-블랙 트리는 완벽한 균형은 아니며, 삽입/삭제 시 색 변경과 회전으로 균형을 유지한다.
• 탐색/삽입/삭제 모두 O(log n)을 보장한다.
• 삽입/삭제 시 회전 횟수가 적으며, 실제 시스템에서 자주 쓰인다.

---

📊 AVL vs RBT 비교

구분	AVL 트리 🌲	레드-블랙 트리 ⚫🔴
균형 유지	엄격 (높이 차 ≤ 1)	느슨 (경로별 Black 수 유지)
탐색 속도	빠름 (더 균형적)	보통 (조금 덜 균형)
삽입/삭제	느림 (회전 많음)	빠름 (회전 적음)
활용 예시	데이터베이스 인덱스	언어 라이브러리, 커널 코드

AVL 트리: 탐색 위주 → 항상 엄격하게 균형 유지
RBT: 삽입/삭제 많은 경우 → 유지 비용 최소화

[참고] AVL과 RBT 모두 O(log n)를 보장하지만, AVL은 더 엄격한 균형으로 탐색이 빠른 대신 삽입/삭제 유지비용이 크고, RBT는 느슨한 균형으로 삽입/삭제가 평균적으로 더 안정적이다!