[자료구조] BST

BST란?

이진탐색트리입니다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브트리에는 작은 값들만 있고 오른쪽에는 큰 값만 있는 정렬된 트리입니다. 항상 정렬이 되어있는 트리입니다.

 

이진트리란?

모든 노드의 자식 노드의 갯수가 2개 이하인 트리

 

조건

- root node의 값보다 작은 값은 왼쪽, 큰 값은 오른쪽

- 모든 subtree도 1번을 만족

 

 

시간 복잡도

평소에 빅오(logn)

worst 빅오(n) - 균형이 깨져서 한쪽으로 치우친 이진탐색트리의 경우엔 Linked List와 다를게 없어진다.