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

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

 

 

 

 

📚 Table of Contents

 

 

 

 

이진 탐색 트리 (Binary Search Tree)

개념

이진 탐색 트리란 아래의 규칙으로 구성된 이진 트리이다.

• 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다.
• 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다.
• 각각의 서브 트리도 이진 탐색 트리를 유지 한다.
• 중복된 키를 허용하지 않는다.

 

 

 

 

특징

• 이진 탐색 트리 규칙에 의해 데이터가 정렬된다.
  • 유일한 키: 모든 노드는 중복되지 않는 키를 갖습니다.
  • 왼쪽 서브 트리: 어떤 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 그 노드의 키보다 작습니다.
  • 오른쪽 서브 트리: 어떤 노드의 오른쪽 서브 트리에 있는 모든 노드의 키는 그 노드의 키보다 큽니다.
  • 서브 트리의 성질: 각 서브 트리 역시 이진 탐색 트리의 모든 성질을 만족해야 합니다.

 

• 이진 트리에 비해 탐색이 빠르다. ( 균형 유지 필요 )
  • 균형 상태 : O(logN)
  • 불균형 상태 : O(N)

 

 

 

 

 

 

 

이진 탐색 트리 - 탐색, 삽입, 삭제

탐색

탐색 연산은 루트 노드에서 시작해, 찾고자 하는 키 값을 가진 노드를 탐색한다.

 

이 과정은 다음과 같습니다:

1. 루트 노드 비교: 루트 노드의 키 값을 찾고자 하는 키 값과 비교한다.
2. 왼쪽 서브 트리 이동: 찾고자 하는 키 값이 루트 노드의 키 값보다 작으면, 왼쪽 자식 노드로 이동한다.
3. 오른쪽 서브 트리 이동: 찾고자 하는 키 값이 루트 노드의 키 값보다 크면, 오른쪽 자식 노드로 이동한다.

 

반복적으로 위 단계를 거쳐 키 값을 찾거나, 더 이상 자식 노드가 없는 리프 노드에 도달할 때까지 수행한다.

 

 

 

 

삽입

이진 탐색 트리에 새로운 노드를 삽입하는 방법은 다음과 같다.

1. Root 부터 비교 시작 ( *중복 키 발견 시 추가하지 않고 종료 *)
2. 삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동
3. 삽입할 키가 현재 노드의 키보다 크면 오른쪽으로 이동
4. Leaf 노드에 도달 후 키 비교하여, 작으면 왼쪽, 크면 오른쪽에 삽입한다.

 

 

 

 

 

삭제

이진 탐색 트리에서 노드를 삭제하는 경우는 세 가지로 나뉜다.

리프 노드 삭제

리프 노드(자식이 없는 노드)를 삭제하는 경우, 그냥 해당 노드를 삭제하면 된다.

 

 

 

한 개의 자식을 가진 노드 삭제

한 개의 자식을 가진 노드를 삭제할 때, 삭제하려는 노드의 부모와 자식을 직접 연결한다.

 

 

 

두 개의 자식을 가진 노드 삭제

가장 복잡한 경우이다.

이 경우 후계 노드(successor) 또는 선행 노드(predecessor)를 찾아 삭제될 노드의 위치에 넣어야 한다.

 

후계 노드는 삭제될 노드의 오른쪽 서브 트리에서 가장 작은 키 값을, 선행 노드는 왼쪽 서브 트리에서 가장 큰 키 값을 의미한다.

1. 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택
2. 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노트 선택

• 1번, 2번 에서 선택한 노드를 삭제 대상 노드 위치로 넣는다.