Binary Search Tree

이진탐색트리

데이터를 저장할 때 큰 데이터를 오른쪽에, 작은 데이터를 왼쪽에 저장하는 방식의 트리구조

규칙

1. 왼쪽 서브트리의 모든 노드는 현재 노드의 값보다 작다.

2. 오른쪽 서브트리에 있는 모든 노드의 값은 현재 노드의 값보다 크다.

3. 각 서브트리도 이진탐색트리이다.

구조

특징

• 재귀적 구조

  이진탐색트리는 재귀적으로 정의되기 때문에, 각 노드의 서브트리도 이진탐색트리이다.

• 시간 복잡도

  최악의 경우 O(n), 일반적으로 균형잡힌 트리의 경우 O(log n)의 시간 복잡도를 갖는다.

  트리의 높이에 따라 시간복잡도는 달라진다.
  (O(n)과 O(log n)의 시간복잡도)

• 삽입과 삭제

  삽입과 삭제 시 트리의 구조를 이진탐색트리의 규칙에 맞도록 재배치 해야한다.

• 변형 트리

  편향성이라는 치명적 단점을 갖고 있기 때문에 이진탐색트리를 기반으로한 다양한 변형트리가 있다(AVL, red black 등)

장점

• 빠른 검색

  평균 시간복잡도 O(log n)으로 원하는 값을 찾을 수 있다. (단, 트리가 균형 잡혀있을 경우)

• 삽입 삭제의 효율성

  평균 시간 복잡도 O(log n)으로 삽입 삭제가 가능하다.

  배열과 달리 삽입 삭제시 주변 노드 몇개의 연결만 바꿔주면 되기 때문에 상대적으로 효율적이다.

• 데이터 정렬

  중위 순회를 통해 데이터를 오름차순 또는 내림차순으로 정렬된 형태로 얻을 수 있다.

단점

• 편향성 문제

  한쪽으로 계속해서 큰 값 또는 작은 값을 삽입할 시 균형이 깨진 편향 이진트리가 될 수 있으며, 이 경우 선형구조와 같아져 시간복잡도가 O(n)으로 증가한다.
  

• 균형유지의 어려움

  트리가 스스로 균형을 유지할 수 있는 규칙이 따로 없기 때문에 위의 편향성 문제가 발생시 해결할 수 없다. 따라서 이를 해결한 변형 트리들이 다수 존재한다.

• 낮은 캐시 효율성

  노드가 메모리의 연속적인 위치에 저장되지 않기 때문에 캐시 효율이 낮다. 따라서 메모리 접근 시간에 부정적 영향을 미칠 수 있다.

이진탐색트리의 활용

그 자체로 활용되기 보다는, 장점은 유지한 채 단점을 보완한 다양한 변형트리들이 실제로 활용된다.

• 데이터베이스 인덱싱

  이진탐색트리를 변형한 B-tree 또는 B+tree 등이 데이터베이스의 인덱싱을 할 때 사용되어 빠르게 데이터를 검색할 수 있다.

• 사전 및 문자열 탐색

  사전 구조나 문자열 탐색에서 trie와 같은 변형트리가 응용되어 효율적으로 검색,삭제,삽입을 할 수 있다.

• 자동 완성 및 추천시스템

  사용자 입력에 따라 관련 항목을 즉각적으로 찾기 위해 이진 탐색트리를 사용한다.