Binary Search Tree(이진 탐색 트리)

이진 탐색 트리를 설명하기에 앞서 트리 구조에 대해 먼저 알아보자.

 

트리 구조란?

• 하나의 루트(root) 노드를 가진다.
• 나머지 노드들은 부모와 자식 관계의 노드들로 간선으로 이어진 계층형 자료 구조이다.

 

이진 트리란?

• 이진 트리는 트리의 모든 차수가 2인 트리를 말한다. 차수는 노드의 서브트리 개수를 말하는데 트리 내부의 서브트리가 항상 2개인 트리를 이진 트리라고 부른다.

 

이진 탐색 트리란?

• 탐색(검색)을 효율적으로 하기 위한 트리 구조
• 이진 트리이며 모든 원소는 서로 다른 유일한 key를 가진다.
• 왼쪽 서브트리의 key값 < 루트의 key값 < 오른쪽 서브트리의 key값의 법칙을 항상 따른다.
• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리 형성

 

1) 탐색 연산

• 탐색할 key값 x를 루트 노드의 key값과 비교

- key값 x = 루트 노드의 key값 -> 탐색 성공

- key값 x < 루트 노드의 key값 -> 왼쪽 서브 트리에 대해서 탐색 연산 수행

- key값 x > 루트 노드의 key값 -> 오른쪽 서브 트리에 대해서 탐색 연산 수행

 

이진 탐색 트리의 탐색(검색) 연산

 

2) 삽입 연산

• 먼저 탐색 연산을 수행 - 삽입할 노드 생성 - 삽입 노드를 부모 노드에 연결

 

재귀적으로 구현한 삽입 연산

 

3) 삭제 연산

• 탐색 연산을 수행 - 탐색하여 찾은 노드를 삭제
• 삭제할 노드의 차수에 따른 경우의 수가 다름

- case 1: 삭제할 노드의 차수가 0 일때 : 부모의 해당 자식 필드를 null로 처리한 후 노드를 삭제

- case 2: 삭제할 노드의 차수가 1 일때 : 삭제될 노드의 자식을 삭제될 노드의 부모 노드에 연결 후 노드 삭제

- case 3: 삭제할 노드의 차수가 2 일때 : 왼쪽 서브트리에서 제일 큰 값 or 오른쪽 서브트리에서 제일 작은 값을 후계자로 선정하고 자리를 물려 줌(제일 효율적으로 이진 탐색 트리의 정의를 지키면서 삭제 가능)

 

삭제할 노드와 부모노드 탐색 -> 삭제할 노드의 차수가 0인 경우

삭제할 노드의 차수가 1인 경우, 삭제할 노드의 차수가 2인 경우

 

이렇게 이진 탐색 트리의 탐색, 삽입, 삭제에 대해서 알아보았다. 다음 시간에는 트리 구조를 활용한 우선순위 큐(힙)에 대해서 알아보자.