이진탐색트리(Binary Search Tree)

이경섭·2022년 10월 18일
0

Algorithm

목록 보기
10/15

이진탐색트리

이진탐색트리란, 정렬이진 트리를 말하며

노드의 왼쪽 서브 트리 노드부모 노드보다 으며, 오른쪽 서브 트리 노드부모 노드보다 크거나 같다.

value(왼쪽서브트리) ≤ value(루트노드) ≤ value(오른쪽서브트리)


탐색

이진탐색트리의 가장 큰 장점은 탐색 시 시간복잡도가 O(logN)이라는 점이다.

위 예시와 같이 탐색할 값노드 값과 비교하여 작으면 왼쪽 서브 트리로, 크면 오른쪽 서브 트리로 이동하여 탐색이 진행된다.

또한 위 그림을 보면 알 수 있듯이 탐색의 연산은 트리의 높이(h)를 넘지 않는다.


삽입

데이터 삽입은 위 그림과 같이 root에 추가, 탐색과 유사한 비교 작업을 통해 삽입 처리를 한다.
따라서 [root 삽입] O(1) + [탐색] O(logN) + [삽입] O(1) 으로 탐색과 동일하게 O(logN)의 시간복잡도를 가진다.


삭제

삭제 연산은 3가지의 경우로 나누어 처리한다.

  1. 삭제하려는 노드가 단말 노드인 경우
  2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있
    는 경우
  3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

1. 삭제하려는 노드가 단말 노드인 경우

위 그림과 같이 삭제하려는 값 탐색 후 제거 하면 된다.

[탐색] O(logN) + [삭제] O(1) 의 연산이므로 탐색, 삽입과 동일하게 O(logN) 의 시간복잡도를 가진다.


2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우

위와 같이 노드 삭제 후 서브 트리를 부모 노드에 붙여주면 된다.

(균형 이진탐색트리가 아닌 경우에는 서브트리를 정렬 해야하는 경우도 생긴다.)


3. 삭제하려는 노드가 두개의 하위 서브 트리를 모두 가지는 경우

위 그림과 같이 왼쪽 서브트리에서의 제일 큰 값오른쪽 서브 트리에서의 제일 작은 값을 비교 후 후계 노드를 선택하여 트리를 재구성한다.


이진탐색트리의 성능

위 그림에 있듯이 최악의 경우는 연결리스트와 다르지 않다.



균형 이진탐색트리


Reference)
파이썬 알고리즘 인터뷰
https://code-lab1.tistory.com/m/10
https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/
http://ivis.kr/images/a/a5/2018_DS_ch09.pdf


정리할 내용:
이진탐색트리 - 정의(속성), 연산(탐색, 삽입, 삭제), 성능(작성 중)
자가균형이진트리 - 정의, AVL트리, 레드 블랙 트리

그림 수정 필요 - 삽입, 삭제2

  • 1차 작성 - 22.10.18 - 이진탐색트리 - 정의, 연산, 성능(작성중)

0개의 댓글