[CS/자료구조] 이진 탐색 트리 (BST)

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

이진 탐색 + 연결 리스트를 결합한 자료구조의 일종

이진 탐색의 효율적인 탐색 능력 + 빈번한 삽입/삭제 가능하도록 고안

이진 탐색 복잡도 : O(logN)

연결리스트의 삽입/삭제 복잡도 : O(1)

속성

각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 가진 노드들로,

각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값의 노드들로 구성되어 있습니다.

중복되는 노드는 없어야 하며, 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리입니다.

순회시에는 중위순회 방식을 사용하면, 이진탐색트리 내의 모든 값들을 정렬된 순으로 읽을 수 있습니다.

• 중위 순회 : 왼쪽 하위 트리 -> root -> 오른쪽 하위트리

연산

검색 / 삽입 / 삭제

생성 / 삭제 / isEmpty / 순회

• 삽입O(h)번 탐색 후 삽입하긴 하지만, 삽입의 계산복잡도는 O(1)이라 무시할만하다
• 항상 리프노드에 삽입
• 검색
• 시간 복잡도 : O(h) (트리의 높이 :h)
• 삭제
  • 그냥 삭제하면됨
    2) 자식노드가 한 개인 경우
  • 해당 노드를 지우고, 해당 노드의 부모와, 해당 노드의 자식을 연결해주면 됨
    3) 자식노드가 두 개인 경우
  • 왼쪽 서브트리의 가장 오른쪽 노드 (왼쪽 서브트리에서 가장 작은 값)
  • 오른쪽 서브트리의 가장 왼쪽 노드 (오른쪽 서브트리에서 가장 큰 값)
  • 중에 원하는 걸로 삭제할 노드를 대체해주면 된다.
• 1) 자식노드가 없는 경우

한계점

이진탐색트리 핵심 연산인 탐색/삽입/삭제의 복잡도는 모두 O(h) 로, 트리의 높이에 따라 수행시간이 결정되는 구조입니다.

그래서 모든 노드가 한 개의 리프노드를 가지는 트리인 경우에는 노드 수와, 트리의 높이가 일치하게 되어 연산의 시간 복잡도가 O(N)이 되게 됩니다.

이렇게 되면 빠르다고 볼 수 없기 때문에, 전체 균형을 맞추는 이진 탐색트리의 일종인 AVL tree가 제안되었습니다.

** AVL트리 정리 예정

요약

이진탐색트리란 이진탐색과 연결리스트를 결합한 자료구조의 일종으로,

효율적인 탐색 및 빈번한 삽입/삭제가 가능하도록 고안된 자료구조입니다.

각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 노드들로,

각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 노드들로 구성되어 있고

왼쪽 오른쪽 서브트리 또한 모두 이진탐색트리입니다.

** O(h) -> O(logn)으로 표현

이진 탐색트리에서 탐색 시간 복잡도는 트리의 높이가 h일 때O(h)가 됩니다.

삽입 시에는, 항상 리프노드에 삽입하며 O(h)번 탐색 후 삽입하기 때문에 시간복잡도는 탐색과 마찬가지로 O(h)입니다.

삭제는 크게 세 가지 경우로 구분할 수 있는데

먼저 자식노드가 없는 경우에는 그냥 삭제하면 되고

자식노드가 한개일 경우에는 삭제하려는 노드의 부모와 자식을 연결해주고 해당 노드를 삭제하면 됩니다.

자식노드가 두 개일 경우에는,

왼쪽 서브트리에서 가장 작은값 혹은 오른쪽 서브트리에서 가장 큰 값을 찾아

둘 중에 원하는 노드로 삭제할 노드를 대체해주면 됩니다.

이진 탐색트리의 한계점은, 중요 연산들의 시간복잡도가 트리의 높이와 관련이 있기 때문에

모든 노드가 한 개의 리프노드를 가지는 경우에는 노드수와 트리 높이가 일치하게 되어 시간복잡도가 O(N)이 됩니다.