[Data Structure] Binary Search Tree

이진 탐색 트리 (Binary Search Tree)

• 트리 자료구조 중 가장 간단한 형태.
• 이진 탐색이 동작할 수 있도록 고안된, 효율적 탐색이 가능한 자료구조
  • 탐색, 삽입, 삭제가 모두 가능
  • 이진트리(탐색 $O(logN)$) + 연결리스트(삽입, 삭제 $O(1)$)
  • 중복된 노드 없음
• 이진 탐색 트리 핵심 연산
  • 검색
    • 트리의 높이가 h일 때 O(h)
  • 삽입
    • 삽입 위치까지 찾아가는 연산 O(h)+ 삽입 연산 O(1) -> O(h)
  • 삭제
    • 자식이 없는 노드인 경우 그냥 삭제
    • 자식이 1개인 노드인 경우 자식 노드의 값으로 대체
    • 자식이 2개인 노드인 경우 왼쪽 서브 트리의 최대값 or 오른쪽 서브 트리의 최소값 중 하나로 대체
• 이진 탐색 트리의 특징
  1. 부모 노드보다 왼쪽 자식 노드가 작음
  2. 부모 노드보다 오른쪽 자식 노드가 큼
  왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 이진 탐색 트리에서 데이터 조회하는 과정 (중위순회 사용)
  1. 루트 노드 방문
  2. 노드의 값이 찾고자하는 값보다
     1. 작으면, 왼쪽 자식 노드는 모두 그보다 더 작으므로 방문할 필요 없음. 오른쪽 노드 방문함.
     2. 크면, 오른쪽 자식 노드는 모두 그보다 더 크므로 방문할 필요 없음. 왼쪽 노드 방문함.
  3. 반복
  4. 찾으면 종료. 자식 노드가 없을 때까지 못 찾았으면 이진 탐색 트리에 원소가 없는 것.
• 시간 복잡도 O(depth)
  • 균형(balanced) 트리: O(logN)
    • AVL Tree: 모든 노드에 대해 좌서브 트리의 높이와 우서브 트리의 높이 차(균형인수의 절대값)가 1을 넘지 않는 트리
    • RedBlack Tree: 노드의 색을 레드 또는 블랙으로 규정한 후 특정 규칙을 바탕으로 균형트리를 만드는 것
  • 편향 트리: O(N)
    • depth(높이)가 높아져 선형 연산에 가까워져 비효율적 → 강제적으로 균형 이진 트리로 만들며 해결→ AVL Tree, RedBlack Tree ... 꺾어서 대칭 맞춤

---

참고링크

• ICPC 신촌 2022 겨울 알고리즘 캠프 - 트리
• https://github.com/seohyun319/CS_I/tree/main/01. DataStructure