이진검색 트리 (Binary Search Tree)

이진 검색 트리

정의

• 이진 탐색 + 연결 리스트

  • 이진 탐색
    • 탐색에 소요되는 시간 복잡도는 O(logN)
    • 하지만 삽입, 삭제가 불가능.
  • 연결 리스트
    • 삽입, 삭제의 시간 복잡도: O(1)
    • 탐색하는 시간 복잡도: O(N)

• 이 두 가지를 합하여 장점을 모두 얻기 위해 고안된 것이 이진 탐색 트리

• 즉, 효율적인 탐색 능력을 가지고 자료의 삽입, 삭제도 가능하게 만드는 것이다.

조건

1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
3. 같은 키 값을 갖는 노드는 없다.
4. 이진 트리의 중위 순회(inorder)로 정렬된 순서를 읽을 수 있다.

작동 원리

1. 검색

1. 루트부터 검색을 진행한다. 이때 선택하는 현재 노드를 p라고 한다
2. p가 null이면 검색에 실패
3. 검색하는 값(key)와 선택한 노드(p)의 키 값을 비교하는데,
   • key == p: 검색에 성공, 종료
   • key < p: 선택한 노드의 왼쪽 자식 노드 대입 (왼쪽으로 검색 진행)
   • key > p: 선택한 노드의 오른쪽 자식 노드 대입 (오른쪽으로 검색 진행)

2. 삽입

1. 루트부터 선택한다. 이때 선택하는 노드를 node라고 한다.
2. 삽입할 키(key)와 선택 노드(node)의 키 값을 비교한다.
   • 값이 같으면: 삽입에 실패. (종료)
   • key 값 < 삽입할 값:
     • 왼쪽 자식 노드가 없으면: 노드 삽입 (종료)
     • 왼쪽 자식 노드가 있으면: 선택한 노드를 왼쪽 자식 노드로 옮긴다
   • key 값 > 삽입할 값:
     • 오른쪽 자식 노드가 없으면: 노드 삽입 (종료)
     • 오른쪽 자식 노드 있으면: 선택한 자식을 오른쪽 자식 노드로 옮긴다.
3. 2로 되돌아간다.

3. 삭제

세 가지 경우의 수에 따라 각각의 상황에 알맞은 처리를 한다.

• 자식 노드가 없는 노드를 삭제하는 경우
  1. 삭제할 노드의 부모노드가 null을 가리키도록 함
  2. 삭제
• 자식 노대르가 1개인 노드를 삭제하는 경우
  1. 삭제할 노드의 부모노드가 삭제할 노드의 자식 노드를 가리키도록 함
  2. 삭제
• 자식 노드가 2개인 노드를 삭제하는 경우
  1. 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다.
  2. 검색한 노드를 삭제 위치로 옮긴다.
  3. 옮긴 노드를 삭제한다
     • 옮긴 노드의 자식 유무, 개수에 따라 위 과정 진행