Binary Search Tree (BST) 개념 및 예시 문제

1. Binary Search Tree (BST) 개념

- 각 노드가 최대 두개의 자식을 갖는 탐색 트리이다.

- 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다.

- 검색 목적 자료구조이므로 모든 노드는 유일한 키를 갖게 됨 

- 부모 노드의 왼쪽과 오른쪽 서브트리도 이진 탐색 트리

 

- 시간복잡도 : O(logn)

 

 

ex) key = [8, 3, 10, 1, 6, 14, 4, 7, 13]

- 이진 탐색 트리는 하나만 존재하는 것이 아닌 여러 개 존재할 수도 있음

 

2. Binary Search Tree (BST) 검색 및 삽입 방법

검색

타겟 데이터가 존재하는 지

찾고자하는 값과 현재 루트 노드의 값 비교
→ 타겟 값이 더 크다면 오른쪽 서브 트리로
→ 타겟 값이 더 작다면 왼쪽 서브 트리로

위 로직을 재귀적으로 반복 수행하여, 루트 노드의 값이 타겟 데이터일 때 까지 탐색한다.

 

삽입

원하는 데이터를 삽입

• 새로운 데이터가 들어갈 자리가 비어있으면 그대로 값을 대입하면 됨
• 비어있지 않은 경우 해당 자리의 노드 값과 비교
  → 삽입할 데이터보다 작다면 왼쪽 자식트리로 이동시키고
  → 삽입할 데이터보다 크다면 오른쪽 자식 트리로 이동하면 된다.

삭제

타겟 데이터를 삭제

중간에 있는 노드를 삭제하는 경우 트리가 중간에 끊기는 등의 상황이 발생할 수 있기 때문에 이를 처리하는 방안이 있어야 한다. 삭제는 세 가지 경우가 있을 수 있는데, 이에 따라 다르게 대처한다.

1. 리프 노드를 삭제하는 경우
→ 그냥 삭제하면 됨

2. 자식 노드가 하나인 노드를 삭제하는 경우
→ 해당 자식 노드를 삭제할 노드의 위치로 끌어올림

3. 자식 노드가 두 개인 노드를 삭제하는 경우
→ 오른쪽 서브 트리의 MIN 값 OR 왼쪽 서브 트리의 MAX 값 중 하나를 삭제할 노드의 위치로 끌어올림

 

 

2. Binary Search Tree (BST) 예시문제 및 답안

 

https://leetcode.com/problems/search-in-a-binary-search-tree/

Search in a Binary Search Tree - LeetCode

https://lulu-developmentlog.tistory.com/105

700. Search in a Binary Search Tree java

 

https://leetcode.com/problems/validate-binary-search-tree/

Validate Binary Search Tree - LeetCode

 

참고 : https://velog.io/@haero_kim/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-Binary-Search-Tree