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

⭐ 이진 탐색 트리 (Binary Search Tree)

1. 이진 탐색 트리란?

모든 노드에 대해서,

• 왼쪽 서브트리 데이터 < 현재 노드 값
• 오른쪽 서브트리 데이터 > 현재 노드 값
  성질을 만족하는 이진 트리 (중복 데이터 원소는 없는 것으로 가정)

vs 이진 탐색 배열

• (장점) 데이터 원소의 추가, 삭제가 용이
• (단점) 공간소요가 큼
  
  

2. 추상적 자료구조

• insert(key, data) : 트리에 주어진 데이터 원소를 추가
• remove(key) : 특정 원소를 트리로부터 삭제
• lookup(key) : 특정 원소 검색
• inorder() : 키의 순서대로 데이터 원소 나열
• min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색
  
  

3. 구조유지

삭제되는 노드가

1. 말단(leaf) 노드인 경우
   1. 그냥 노드를 없애면 됨
      1. 부모 노드의 링크를 조정(좌?우?)
2. 자식이 하나인 경우
   1. 삭제되는 노드 자리에 그 자식을 대신 배치
      1. 자식이 왼쪽인지? 오른쪽인지?
      2. 부모 노드의 링크를 조정(좌?우?)
3. 자식이 둘인 경우
   1. 삭제되는 노드보다 바로 다음 큰 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제
   
   

4. 효율성

비효율적인 경우

T = BinSearchTree()
T.insert(1, 'John')
T.insert(2, 'Mary')
T.insert(3, 'Anne')
T.insert(4, 'Peter')

• 트리가 한쪽으로 치우치게 되면 탐색시간이 더 걸린다
  → 높이가 비슷하면서, 왼쪽 오른쪽이 균형잡힌 노드의 수여야 한다

더 나은 성능의 이진 탐색 트리

• 높이의 균형을 유지함으로써, O(logn)의 탐색 복잡도 보장
• 삽입, 삭제 연산이 보다 복잡
• AVL tree - https://ko.wikipedia.org/wiki/AVL_트리
• Red-black tree - https://ko.wikipedia.org/wiki/레드-블랙_트리