이진탐색트리(Binary search tree,BST)의 시간복잡도

이진 탐색 트리 : 왼쪽자식은 root보다 항상 값이 적고, 오른쪽은 큰 값이 들어가게 되는 순서를 만족하는 것. 한번 입력이 되게 되면 자리를 바꾸지 않음. 주로 데이터 검색에 사용하며 탐색 속도를 개선할 수 있음.

그러나 맨 첫번째 항목이 어떤 항목이 삽입되느냐에 따라 이진탐색트리는 한쪽으로 쏠리는 불균형 현상이 일어날 수 있음. 지금 현재있는 것과 비교해서 왼쪽으로갈지 오른쪽으로 갈지 정함.(완전이진트리처럼 왼쪽부터 채우지 x)

 

그래서 최악의 경우 복잡도를 고려해 균형화 작업을 하는 것이 좋다.

균형화 : height difference의 절댓값이 1이하이도록 작업하는 것.

항목	균형화하지 않을 때	균형화할 때
탐색(search)	-평균: O(log N) -최대: N/2 =>O(N)	-평균: O(log N) -최대: O(log N)
트리노드 삽입(insert)	-평균:O(log N) -최대:O(N)	-평균:O(log N) -최대:O(log N)
트리노드 삭제(erase)	-평균:O(log N) -최대:O(N)	-평균:O(log N) -최대:O(log N)

 

 

균형화를 하지않으면 최악의 경우 연결형 리스트와 같이 동작하여 O(N)의 시간복잡도. 따라서 트리노드 삽입/삭제를 할 때 트리모양을 균형있게 만들어주는 작업을 시키면 시간복잡도가 O(N)이 되는 것을 방지할 수 있다.