이진 탐색 트리

정의

• 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것

탐색 연산

• 1️⃣ 루트에서 시작 ( 키값 = x, 루트 노드의 키값 = y )
  • x = y : 탐색 연산 성공
  • x < y : 루트 노드의 왼쪽 서브트리에 대해 탐색 연산 수행
  • x > y : 루트 노드의 오른쪽 서브트리에 대해 탐색 연산 수행

삽입 연산

• 1️⃣ 탐색 연산 수행
  • 같은 원소가 트리에 있으면 삽입 불가하기에, 탐색하여 확인
• 2️⃣ 탐색 실패가 결정되는 위치에 삽입 연산 수행

삭제 연산

• 1️⃣ 탐색 연산 수행

  • 삭제할 노드 위치 확인

• 2️⃣ 탐색하여 찾은 노드 삭제

  • 차수 = 0 ( 단말 노드 ) → 그냥 지우면 된다.

  • 차수 = 1 ( 자식 1개 ) → 후속처리, 자식이 하나라 그냥 노드 자리를 물려 주면 된다.

  • 차수 = 2 ( 자식 2개 ) → 후속처리, 자식이 두개라 후계자 선택을 해야함. 가짓수는 두개겠지?

    

• 후계자 선택 방식 → 히프의 구조(특징)을 유지한다. 그냥 히프를 지워보면 아니까 패스.

  • 왼쪽 서브트리에서 가장 큰 자손 노드 선택
  • 오른쪽 서브트리에서 가장 작은 노드 선택

히프

정의