[C++][자료구조] Binary Tree(이진트리)란 ? 구현법은 ?

*Binary Search Tree(이진 탐색 트리)

: 이진 탐색이 동작할 수 있도록 고안된 자료구조.

: 모든 key값은 유일하고, 값의 크기는 '왼쪽자식 노드 < 부모 노드 < 오르쪽 자식 노드' 순을 가짐.

 

*이진 트리의 예

값의 크기를 왼쪽자식 노드 < 부모 노드 < 오르쪽 자식 노드 순으로 갖고 있기 때문에 위 트리는 이진트리이다.

 

*이진 탐색 트리 방법

30을 찾는다고 가정해보자.

1) 루트노드인 20부터 탐색한다.

2) 30은 20보다 큰 수이므로 오른쪽 서브트리를 탐색한다.

3) 23보다 30이 큰 수이므로 23의 오른쪽 서브트리를 탐색한다.

4) 30 찾음 !

: 기존엔 모든 노드를 탐색해야했다면, 이진 트리이기에 탐색을 반으로 줄여가며 탐색할 수 있다. O(log₂N)

but, 자식노드들이 한쪽으로 모두 편향되어 있는 이진 트리라면 노드 전부를 탐색해야 하므로 O(n)의 시간복잡도가 나온다.(아래 사진 참고)

*이진트리 탐색/삽입/삭제 c++코드

https://ansohxxn.github.io/algorithm/bst/