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

정의

왼쪽 서브 트리의 모든 값이 부모 노드보다 작고, 오른쪽 서브 트리의 모든 값이 부모 노드보다 큰 이진 트리

• 서브 트리 : 자식 노드로부터 뻗어나가는 하위 트리
• 이진 트리 : 자식이 최대 2개까지 있는 트리 구조

 

특징

• 삽입, 삭제, 탐색, 갱신 모두 O(logN)의 시간이 걸린다.
  • 단, 한쪽 부분에 값이 몰리는 편향이 발생할 수 있는데, 이 편향이 심해질수록 성능이 저하된다.
• 삽입 시 자동으로 원소가 크기 순으로 정렬되어 저장된다.
  • 특정 노드보다 작거나 큰 최초의 노드가 무엇인지 O(logN)에 알아낼 수 있다.
• 편향된 이진 트리를 균형 있게 다시 배치해 편향을 해소한 트리를 자가 균형 트리라 한다.
  • 대표적으로 AVL트리와 Red Black 트리가 있다.
• O(N^2)보다 빠른 속도로 데이터의 대소 관계가 필요한 경우 유용하게 쓸 수 있다.
  • 또한 삽입/삭제 연산도 빈번하게 일어난다면 활용도가 더욱 높아진다.