[Data Structure] 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리(Binary Search Tree, BST)는 트리 자료구조의 한 형태로, 이진 탐색 알고리즘의 원리를 적용한 자료구조이다. 즉, 이진 탐색 트리는 이진 트리(Binary Tree)의 특성을 기반으로 하여 데이터의 효율적인 탐색, 삽입, 삭제를 가능하게 한 구조입니다. 그러나 트리의 균형이 맞지 않으면 성능이 저하될 수 있어 AVL 트리, 레드-블랙 트리와 같은 자가 균형 이진 탐색 트리가 사용되기도 한다.

 

 

이진 탐색 트리의 표현

---

이진 탐색 트리(Binary Search Tree)는 트리 자료구조의 한 형태로 다음 조건을 만족하는 트리이다.

• 중복 데이터를 허용하지 않는다.
• 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값의 노드들만 포함된다.
• 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값의 노드들만 포함된다.

이진 탐색 트리

 

 

이진 탐색 트리의 특징

---

1. 데이터의 정렬된 상태를 유지
이진 탐색 트리는 데이터를 삽입하는 동시에 정렬된 상태를 유지한다. 이진 탐색 트리를 중위 순회(In-Order Traversal) 할 경우 데이터가 오름차순으로 출력된다.

 

2. 데이터의 효율적인 탐색

이진 탐색 트리는 이진 탐색 알고리즘의 원리를 적용하여 탐색 연산의 평균 시간 복잡도가 O(log N)으로 줄어들며, 이는 트리의 높이에 비례한다.

 

3. 빠른 삽입과 삭제 

이진 탐색 트리의 삽입, 삭제 연산은 데이터를 탐색하는 데 이진 탐색의 원리를 사용하여 평균적으로 O(log N)의 시간 복잡도를 가진다. 삽입과 삭제 과정에서 노드를 연결하는 작업은 각각 O(1)의 시간 복잡도를 가지기 때문에 최종적으로 삽입과 삭제 연산의 평균 시간 복잡도는 O(log N)이며, 이는 트리의 높이에 비례한다.

 

 

이진 탐색 트리의 한계

---

이진 탐색 트리는 삽입 순서에 따라 매우 불균형한 형태로 변형될 수 있다. 이진 탐색 트리의 탐색, 삽입, 삭제 연산은 트리의 높이에 비례하기 때문에 선형 구조(편향 이진 트리)와 비슷해 질 수록 시간 복잡도가 O(N)으로 증가하게 된다.

불균형한 이진 트리

 

 

이를 해결하기 위해 트리의 불균형을 조절하는 자가 균형 이진 탐색트리가 고안되었으며, 대표적으로 다음과 같은 트리 자료구조가 존재한다.

• AVL 트리: 삽입 및 삭제 시 균형을 유지하기 위해 회전 연산을 사용합니다.
• 레드-블랙 트리: 균형 유지와 함께 삽입, 삭제 연산의 최악 시간 복잡도를 O(log n)으로 보장합니다.
• B-트리: 다중 자식 노드를 허용하여 데이터베이스 및 파일 시스템에서 효율적인 탐색을 지원합니다.

 

 

이진 탐색 트리의 구현

---

[탐색 연산]

탐색 연산은 주어진 키 값을 갖는 노드를 찾는 과정이다. 탐색 연산은 루트 노드에서 시작하여 다음 과정을 진행한다.

• 현재 노드의 값과 주어진 키 값을 비교한다.
• 키 값이 현재 노드의 값보다 작다면 왼쪽 자식 노드로 이동한다.
• 키 값이 현재 노드의 값보다 크다면 오른쪽 자식 노드로 이동한다.
• 현재 노드가 NULL 또는 주어진 키 값과 동일할 때 까지 위 과정을 반복한다.
  (현재 노드가 NULL 이라면 탐색 실패로 주어진 키 값이 이진 탐색 트리에 저장되어 있지 않다는 의미이다.)

이진 탐색 트리 - 탐색 연산 과정

- C++ Code

추가 예정

 

 

[삽입 연산]

삽입 연산은 새로운 값을 트리에 추가하는 과정이다. 루트 노드에서 시작하여 다음 과정을 진행한다.

• 현재 노드의 값과 삽입할 값을 비교한다.
• 삽입할  값이 현재 노드의 값보다 작다면 왼쪽 자식 노드로 이동한다.
• 삽입할  값이 현재 노드의 값보다 크다면 오른쪽 자식 노드로 이동한다.
• 현재 노드가 NULL 일때 까지 위 과정을 반복한다.
• 현재 노드가 NULL 인경우 새로운 노드를 생성하여 연결한다.

이진 탐색 트리 - 삽입 연산 과정

- C++ Code

추가 예정

 

 

[삭제 연산]

삭제 연산은 특정 값을 갖는 노드를 트리에서 제거하는 과정이다. 루트 노드에서 시작하여 다음 과정을 진행한다.

• 현재 노드의 값과 삽입할 값을 비교한다.
• 삽입할  값이 현재 노드의 값보다 작다면 왼쪽 자식 노드로 이동한다.
• 삽입할  값이 현재 노드의 값보다 크다면 오른쪽 자식 노드로 이동한다.
• 현재 노드가 삭제할 값과 같을 때 까지 위 과정을 반복한다.
• 현재 노드를 다음 조건에 따라 삭제한다.
  1) 자식 노드가 없는 경우 : 현재 노드를 삭제한다.
  2) 자식 노드가 하나인 경우 : 현재 노드를 삭제하고 현재 노드의 자식 노드와 부모노드를 연결한다.
  3) 자식 노드가 둘인 경우 : 현재 노드의 오른쪽 서브 트리에서 최소값을 찾은 후 현재 노드의 값과 교체한다.
                                                그 다음 오른쪽 서브 트리에서 최소값 노드를 삭제한다. 

 

- 자식 노드가 없는 경우 삭제 연산

 

- 자식 노드가 하나인 경우 삭제 연산

 

- 자식 노드가 둘인 경우 삭제 연산

 

- C++ Code

추가 예정