BST (Binary Search Tree)

목표

• 활주로 예약 문제를 통해 기존 자료 구조의 한계를 파악한다.
• 이진 탐색 트리의 개념을 이해한다.
• 이진 탐색 트리의 삽입, 탐색 등의 방법을 이해한다.
• 이진 탐색 트리를 사용한 활주로 예약 문제의 해법을 살펴보며, 한계점을 짚어본다.

---

[문제] 활주로 예약 하기

• 활주로가 하나뿐인 공항에서 착륙 시간을 예약하는 시스템에 대해 생각해보자.
• 예약에 대한 리퀘스트가 왔을 때, 시점 앞뒤로 k분 이내에 예약이 없을 때만 시스템에 등록이 된다.
• 예시)
  • 현재 시점은 37이며, 예약 명단이 [41, 46, 49, 51]이며, k = 3일때
  • -> 44 : not allowed
  • -> 53 : ok
  • -> 22 : not allowed (already past)
• log(n)의 시간 안에 예약을 완료할 수 있는 방법이 있을까??

어떤 방법들이 가능할까?

• sorted array
  • 탐색) binary search로 빠른 탐색이 가능 (log(n))
  • 삽입) array에 데이터 삽입/삭제 시 o(n)의 시간 복잡도 (삽입/삭제 후 이동 필요)
• sorted list(linked list)
  • 탐색) o(n)의 시간 복잡도가 필요
    • 일반적인 리스트에서는 임의접근이 불가능함
    • 따라서 binary search를 할 수 없음
  • 삽입) 포인터만 수정해주면 되므로 삽입/삭제에 o(1)의 시간복잡도가 필요
• heap
  • 삽입) 삽입은 O(log(n)) 시간 안에 가능
    • 리프 노드에 추가하고 max heap 조건을 만족하도록 트리를 수정
    • (루트까지 올라가면서 key값을 비교 & swap 수행하는 작업)
  • 하지만 "k분 이내에 다른 예약"을 체크하기 위해서 o(n)의 시간복잡도 필요
• 위의 방법들로는 탐색/삽입을 log(n)시간 안에 완료할 수 없다.
• 탐색/삽입을 동시에 효율적으로 할 수 있는 새로운 방법이 필요하다.

이진 탐색 트리(Binary Search Tree)란?

• 이진 탐색 트리(BST : Binary Search Tree)는 이진 탐색(Binary search)과 linked list를 결합한 자료구조이다.
• BST는 탐색의 효율성이 유지되면서도 linked list를 사용하였기 때문에 데이터의 삽입/삭제도 용이하다.
• 이진 탐색 트리(BST)는 아래와 같은 속성을 지닌다.
  • 각 노드는 key 값을 지닌다.
  • 루트 노드를 제외한 모든 노드는 부모 노드(parent(x))를 가진다.
  • 노드는 왼쪽/오른쪽 자식을 가지는데, 힙과 다른 점은 포인터로 구성된다는 점이다.
  • 각 노드의 왼쪽 서브트리에는 해당 노드의 키값보다 작은 노드들로 이루어져 있다.
  • 각 노드의 오른쪽 서브트리에는 해당 노드의 키값보다 큰 노드들로 이루어져 있다.

이진 탐색 트리(BST)를 사용한 작업

• insert(val)

  • 삽입지점을 찾을때까지 트리를 찾아 따라 내려간다.

• find(val)

  • 값을 찾을때까지 트리를 따라 내려간다.

• findmin()

  • 더이상 노드가 없을때까지 왼쪽으로 따라 내려간다.

• next_larger()

  • 오른쪽 노드가 nil이 아니면 오른쪽 서브트리에서 제일 작은 값을 찾는다.

  • 오른쪽 노드가 nil이면, 자신이 부모의 오른쪽 자식인지 체크

  • 오른쪽 자식이면 부모노드로 이동. 자신이 왼쪽 자식이 될때까지 이동하며, 왼쪽 자식일때는 부모값을 리턴한다.

  • psuedo code

      if right child is not NIL, return minimum(right)
      else y = parent(x)
      while y is not NIL and x = right(y)
      x = y; y = parent(y)
      return (y)

• rank(t) : t 보다 작은 노드의 개수 찾기

  • 기본적인 이진 탐색 트리(vanila BST)로는 풀기 쉽지 않은 문제
  • 대신 BST를 확장하여, 노드의 삭제 / 삽입 시 각 노드의 서브 트리의 개수를 기록해두면 이런 작업을 쉽게 할 수 있다.

이진 탐색 트리의 한계점

• 이진 탐색 트리에서 탐색/삽입/삭제의 시간복잡도는 o(h)이다.
• 문제는 이진 탐색 트리는 완전 균형 트리가 아니라는 점이다.
• 아래와 같이 순서되로 삽입된 경우(최악의 경우), 트리의 높이가 n이 될 수 있다.
  

  

• 탐색/삽입/삭제가 효율적으로 되려면 트리의 높이가 log(n)로 유지되어야한다.