[자료구조/알고리즘] 이진 탐색 트리(Binary Search Tree)

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

• 정의
  - 아래의 규칙으로 구성된 이진트리
  • 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
  • 오른쪽 자식노드의 키는 부모 노드의 키보다 큼
  • 각 서브 트리도 이진 탐색 트리 구조를 유지
  • 중복된 키를 허용하지 않음
• 특징
  - 이진 탐색 트리 규칙에 의해 정렬됨
  - 이진 트리에 비해 탐색이 빠름(균형 유지 필요)
  -> 균형 상태: O(logN), 불균형 상태: O(N)
  

탐색 방법

• 찾고자 하는 데이터를 루트 노드부터 비교 시작
• 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동
• 찾는 데이터가 없으면 null을 반환
• 어떤 데이터를 찾더라도 트리의 최대 높이만큼 탐색이 이루어짐

삽입 방법

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

삭제 방법

• 삭제 대상 노드가 Leaf노드인 경우
  - 삭제 대상 노드 삭제
  - 부모 노드의 해당 자식 링크를 null로 변경
• 삭제 대상 노드가 자식 노드를 가진 경우
  - 자식 노드를 삭제 대상 노드의 부모 노드에 연결
  - 삭제 대상 노드 삭제
• 삭제 대상 노드에 자식 노드가 둘인 경우
  방법 1. 삭제 대상 노드의 왼쪽 서브트리에서 가장 큰 노드 선택
  방법 2. 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택
  - 방법 1또는 방법 2에서 선택한 노드를 삭제 대상 노드 위치로 변경
  - 삭제 대상 노드 삭제