이진 탐색 트리(binary search tree)

 

이진 탐색 트리(binary search tree)란?

 

모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고

모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 더 큰 값들만 가지는 트리

 

👉 이진 탐색 트리의 최솟값

트리의 가장 왼쪽에 존재

 

👉 이진 탐색 트리의 최댓값

트리의 가장 오른쪽에 존재

 

👉 노드의 successor(후임자)

해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드

 

👉 노드의 predecessor(선임자)

해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드

 

👉 이진 탐색 트리 순회하는 방법

이진 탐색 트리에서는 중위 순회를 대체로 사용함!

트리의 탐색 방법에는 3가지가 있음

 

inorder traversal (중위 순회)

재귀적으로 왼쪽 서브 트리 순회

현재 노드 방문

재귀적으로 오른쪽 서브 트리 순회

각각의 노드들을 순서(왼쪽에서 오른쪽 순으로 = 크기순)대로 방문하게 됨!

 

preorder traversal (전위 순회)

현재 노드 방문

재귀적으로 왼쪽 서브 트리 순회

재귀적으로 오른쪽 서브 트리 순회

 

postorder traversal (후위 순회)

재귀적으로 왼쪽 서브 트리 순회

재귀적으로 오른쪽 서브 트리 순회

현재 노드 방문

 

 

이진 탐색 트리의 삽입 / 삭제 / 검색

삭제

삭제하려는 노드가 있는지 검색이 필수!

있으면 삭제 가능

 

👉 자녀가 없는 노드 삭제

삭제될 노드를 가리키던 레퍼런스를 가리키는 것이 없도록 처리

 

👉 자녀가 1개 있는 노드 삭제

삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀를 가리키게 변경

 

👉 자녀가 2개 있는 노드 삭제

삭제될 노드의 오른쪽 서브 트리에서 제일 값이 작은 노드가 삭제될 노드를 대체한다

or 삭제될 노드의 왼쪽 서브 트리에서 제일 값이 큰 노드가 삭제될 노드를 대체한다

 

👉  이진 탐색 트리의 시간 복잡도

	best	avg	worst
insert	O(1)	O(logN)	O(N)
delete	O(1)	O(logN)	O(N)
search	O(1)	O(logN)	O(N)

 

이진 탐색 트리 장단점

장점

• 삽입 삭제가 유연하다
• 값의 크기에 따라 좌우 서브 트리가 나눠지기 때문에 삽입/삭제/검색이 (보통은) 빠르다
• 값의 순서대로 순회가 가능하다

단점

• 트리가 구조적으로 한쪽으로 편향되면 삽입/삭제/검색 등등 여러 동작들의 수행 시간이 악화된다
• 이를 해결하기 위해 스스로 균형을 잡는 이진 탐색 트리가 사용됨 (AVL 트리, Red-Black 트리 -> O(logN))