참고자료

• https://engineerinsight.tistory.com/321#%F0%9F%92%8B%C2%A0%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89%20%ED%8A%B8%EB%A6%AC-1

1. 이진 탐색 트리란?

이진 탐색 트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이다.
이진 탐색 트리는 다음과 같은 속성을 지니고 있다.

• 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브 트리, 오른쪽 서브 트리 또한 이진 탐색 트리이다.

이진 탐색 트리는 '데이터베이스 인덱스', '자동 완성 기능'에서 활용한다.
데이터베이스에서 인덱스는 데이터 검색을 빠르게 하기 위한 자료구조이다. 인덱스는 이진 탐색 트리를 활용하여 구현되는데, 인덱스를 효율적인 사용하여 데이터베이스의 검색 성능을 높이기 위해이진 탐색 트리를 사용한다.
자동 완성 기능은 입력된 문자열을 이진 탐색 트리에 저장하여 검색할 때, 빠르게 일치하는 문자열을 찾아내는 방식으로 동작한다.

2. 이진 탐색 트리 알고리즘

• 트리 탐색 알고리즘은 대체로 두 가지 범주로 분류할 수 있다.
  • 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘
    • 루트 노드에서 시작하여 선택한 노드의 가능한 한 깊이까지 한 가지 분기의 모든 노드를 먼저 방문한 다음 다음 분기로 넘어가는 방식
    • 깊이 우선 탐색(DFS) 알고리즘에는 세 가지 변형이 있다.
      • 전위 순회(현재-왼쪽-오른쪽) : 왼쪽 또는 오른쪽 서브 트리 내의 노드를 방문하기 전에 현재 노드를 방문
      • 중위 탐색(왼쪽-현재-오른쪽) : 왼쪽 서브 트리 내의 모든 노드를 방문한 후 오른쪽 서브 트리 내의 노드를 방문하기 전에 현재 노드를 방문
      • 후위 순회(왼쪽-오른쪽-현재) : 왼쪽 및 오른쪽 서브 트리의 모든 노드를 방문한 후 현재 노드를 방문
  • 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘
    • 루트 노드에서 시작하여 트리의 다음 깊이로 이동하기 전에 현재 깊이의 모든 노드를 방문하는 방식

3. 이진 탐색 트리 연산

(1) 탐색

• 탐색은 아래의 과정에서 탐색에 성공할 때까지 계속해서 반복한다.
  • 탐색하려는 값이 루트 노드의 키 값과 같으면 탐색에 성공한다.
  • 탐색하려는 값이 루트 노드의 키 값보다 작으면 왼쪽 서브트리를 탐색한다.
  • 탐색하려는 값이 루트 노드의 키 값보다 크면 오른쪽 서브트리를 탐색한다.
• 이 과정에서 데이터를 발견하지 못하면 탐색에 실패한다.

(2) 삽입

• 먼저 삽입하려는 데이터를 탐색해야 한다. 데이터가 이미 존재한다면 삽입할 수 없기 때문에, 탐색을 하다가 실패해 NULL을 반환받은 그 위치에 데이터를 삽입한다.

(3) 삭제

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

• 삭제될 노드를 가리키던 레퍼런스를 가리키는 것이 없도록(NULL) 처리
  

2) 삭제할 노드가 1개의 자녀 노드만 가지고 있는 경우

• 삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀 노드를 가리키도록 변경
  

3) 삭제할 노드가 2개 이상의 자녀 노드를 가지고 있는 경우

• 삭제될 노드의 오른쪽 서브 트리에서 제일 값이 작은 노드가 삭제될 노드를 대체한다.