Algorithm
-
왜 unbalanced binary search tree는 나쁠까?TECH/Algorithm 2021. 9. 20. 13:03
Why an unbalanced binary search tress is bad? 일반적으로 binary search tree는 조회(lookup), 삽입(insert), 삭제(delete)에 O(logN)이 소요되는 자료구조 이다. 하지만, 아래 그림과 같이 이진 검색 트리가 한 쪽으로 편항될 경우, 사실상 링크드 리스트와 다를게 없게 된다. 따라서 조회(lookup), 삽입(insert), 삭제(delete)에 O(N)이 소요되어 성능의 저하가 발생한다.