[자료구조] 트리 2 - 이진 탐색 트리 with Python

앞서 봤던 트리들에서 탐색 효율을 높이기 위해 사용하는 '이진 탐색 트리'에 대해서 알아보자.

 

목차

1. 이진 탐색 트리?

2. 연산

3. 성능

---

1. 이진 탐색 트리?

• 탐색 작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 가진다.
• key(왼쪽 서브 트리) < key(루트 노드) < key(오른쪽 서브 트리)
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리
• 중위 순회하면서 오름차순으로 정렬된 값을 얻을 수 있다.

 

---

2. 연산

 

탐색 연산

• 루트에서 시작한다.
• 탐색할 키 값 x를 루트 노드의 키 값과 비교한다.
  • (키 값 x = 루트 노드의 키값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공
  • (키 값 x < 루트 노드의 키값)인 경우 : 루트노드의 왼쪽 서브 트리에 대해서 탐색연산 수행
  • (키 값 x > 루트노드의 키값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색연산 수행
• 서브트리에 대해서 순환적으로 탐색 연산을 반복

13 탐색

 

삽입 연산

1. 우선 탐색 연산을 수행
   • 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.
   • 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치
2. 탐색 실패한 위치에 원소를 삽입

5를 삽입하는 예

---

 

3. 성능

• 탐색(searching), 삽입(insertion), 삭제(deletion) 시간은 트리의 높이만큼 시간이 걸린다
  • O(h) : h = BST의 깊이(Binary Searching Tree)
• 평균의 경우
  • 이진트리가 균형적으로 생성되어 있는 경우
  • O(log n)
• 최악의 경우
  • 한쪽으로 치우친 경사 이진트리의 경우
  • O(n)
  • 순차 탐색과 시간 복잡도가 같다.

 

# 검색 알고리즘 성능 비교

• 배열에서의 순차 검색 : O(N)
• 정렬된 배열에서의 순차 검색 : O(N)
• 정렬된 배열에서의 이진 탐색 : O(logN)
  • 고정 배열 크기와 삽입 삭제 시 추가 연산 필요
• 이진 탐색 트리에서의 평균 : O(logN)
  • 최악 : O(N)
  • 완전 이진트리 or 균형 트리로 바꿀 수 있다면 최악의 경우 없앨 수 있음
    • 새로운 원소를 삽입할 시 삽입 시간 줄일 수 있음
    • 평균과 최악의 시간이 같다 : O(logN)
• 해쉬 검색 : O(1)
  • 추가 저장 공간이 필요

 

평상시 검색을 위해 어떤 알고리즘을 사용하느냐에 따라 걸리는 시간이 다르지만 무조건 빠르다고 좋은 것은 아닌 것 같다!

각 검색 방법의 장단점을 확실히 알고, 상황에 맞게 사용하자