이진 탐색 트리

목적

이진 탐색 + 연결 리스트

이진 탐색 : 탐색에 소요되는 시간 복잡도 O(logN), but 삽입 삭제 불가능

연결 리스트 : 삽입, 삭제의 시간 복잡도 O(1), but 탐색하는 시간 복잡도 O(N)

이 두 개를 합쳐 장점을 모두 얻는 것이 이진 탐색 트리

→ 효율적인 탐색 + 자료 삽입 삭제도 가능

특징

• 각 노드의 자식이 2개 이하

• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼

• 중복된 노드가 없어야 함

  • 검색 목적 자료구조인데, 중복이 많으면 검색 속도가 오래 걸림

• 중위 순회 방식(왼쪽 - 루트 - 오른쪽)

  → 정렬된 순서를 읽을 수 있음
  

핵심 연산

• 검색
• 삽입
• 삭제
• 트리 생성
• 트리 삭제

시간 복잡도

• 균등 트리 : O(logN)
• 편향 트리 : O(N)
• 삽입, 검색, 삭제 시간 복잡도는 트리의 Depth에 비례함

삭제 Case

1. 자식이 없는 leaf 노드 : 그냥 삭제
2. 자식이 1개인 노드 : 지워진 노드에 자식 올리기
3. 자식이 2개인 노드 : 오른쪽 자식 노드에서 가장 작은 값or왼쪽 자식 노드에서 가장 큰 값 올리기