💿자료구조 - 이진 탐색 트리

탐색트리란?

: 탐색을 위한 트리기반의 자료구조

 

 

이진 탐색이란?

반을 쪼갬 -> 23이 26보다 작으니 왼쪽에 있겠군 -> 17보다 크니 오른쪽에 있겠군 -> 23이 여기있네!

 

 

 

이진 탐색 트리 

: 좌측 서브 트리 값 < 임의 노드 (루트) 값 < 우측 서브 트리 값

 

 

힙 Heap vs 이진 탐색 Binary Search

1. 힙은 부모 - 자식 간 데이터 크기에 중시 ( ex) 맥스힙은 부모가 자식보다 커야 함)

      but 이진 탐색 트리는 한 노드를 기준으로 양쪽 자식간의 데이터 크기에 제한 조건

2. 힙은 완전 트리 조건을 충족해야하나,

    이진트리는 상관 X

3. 힙은 중복을 허용하나,

     이진 탐색 트리는 중복을 허용하지 않음

 

 

 

< 이진 탐색트리에서의 원소 삽입 >

- 이진 탐색 트리의 루트 노드로부터 출발

- 삽입하고자 하는 값과 현재노드의 값을 반복해서 비교하며, 점점 내려감

 

예시 1 ) 35 삽입

 

예시 2) 10 삽입

 

예시 3) 82 삽입

 

 

 

 

 

< 이진 탐색 트리에서의 원소 삭제 >

- 제거하고자 하는 대상 노드가 자식 노드를 가지는 지 확인

 

 [ 가능한 경우의 수 ]

  1. 자식이 없는 노드 제거 : 단순 삭제

 

 

 

  2. 좌측 또는 우측 자식만 존재하는 노드 제거 : 좌측 서브트리의 최대 원소 / 우측 서브트리의 최소 원소로 교체 

 > "임의 노드의 좌측 서브 트리에는 자신보다 작은 값만 존재"해야 한다는 이진 탐색 트리 정의에 의해 

 > 91 을 루트노드로 가지는 서브 트리 중에서 최대원소인 83으로 교체 

"

 

 

  3-1. 좌우측 자식이 모두 존재하는 노드 제거 (방법 1)

 > "임의 노드의 좌측 서브 트리에는 자신보다 작은 값만 존재"해야 한다는 이진 탐색 트리 정의에 의해

 > 35를 루트노드로 가지는 서브 트리 중에서 최대원소인 30으로 교체 

 

 

  3-2. 좌우측 자식이 모두 존재하는 노드 제거 (방법 2)

 > "임의 노드의 우측 서브 트리에는 자신보다 큰 값만 존재"해야 한다는 이진 탐색 트리 정의에 의해

 > 55를 루트노드로 가지는 (오른쪽) 서브 트리 중에서 최소원소인 59으로 교체