왜 unbalanced binary search tree는 나쁠까?

Why an unbalanced binary search tress is bad?

일반적으로 binary search tree는 조회(lookup), 삽입(insert), 삭제(delete)에 O(logN)이 소요되는 자료구조 이다.

하지만, 아래 그림과 같이 이진 검색 트리가 한 쪽으로 편항될 경우, 사실상 링크드 리스트와 다를게 없게 된다.

unbalanced binary search tree

 

따라서 조회(lookup), 삽입(insert), 삭제(delete)에 O(N)이 소요되어 성능의 저하가 발생한다.