이진 탐색 트리

규칙

모든 원소는 서로 다른 유일한 키를 가진다.(중복값 x)

왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다.

오른쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 크다.

왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

 

 

루트에서 시작해서

탐색할 키값 x를 루트 노드의 키 값과 비교

x ==  루트 키값

연산 완료

x <  루트 키값

작으면 왼쪽으로

x >  루트 키값

크면 오른쪽으로

 

 

---

이진 탐색 트리의 삽입 연산

 

1) 먼저 탐색 연산 수행

- 고유 키값 규칙, 트리에 없어야 삽입 가능

2) 탐색 실패한 위치에 원소를 삽입

---

이진 탐색 트리의 삭제 연산

1) 탐색 연산 수행

2) 노드 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업) 가 필요함

• 삭제할 노드가 단말 노드인 경우(차수 =0)
  • 단순 삭제 및 포인터 처리
• 삭제할 노드가 자식 노드를 한 개 가진 경우(차수 =1)
  • 삭제 노드 탐색 후 부모 노드와 자식 노드의 연결 필요

 

• 삭제할 노드가 자식 노드를 두 개 가진 경우(차수 =2)
  • 후계자 선택 방법
    • 왼쪽 서브 트리에서 가장 큰 자손 노드 선택 :
      왼쪽 서브트리의 오른쪽 링크를 따라 계속 이동하여 오른쪽 링크필드가 NULL 인 경우 대상으로 지정
    • 오른쪽 서브트리에서 가장 작은 자손 노드 선택:
      오른쪽 서브트리의 왼쪽 링크를 따라 계속 이동하여 왼쪽 링크필드가 NULL 인 경우 대상으로 지정

 

삭제 후 후처리 과정 상 반복작업 : 자식이 있을 수 있음

• 재귀호출 필요