komabomin   2년 전

시간초과 뜨는 이유를 모르겠습니다..... 코드 보고 조언이나 수정 좀 해주세요 ㅜㅜ


chogahui05   2년 전

이 문제 굉장히 어렵지요?? 물론 전 풀지 않았습니다.

간단하게 테스트 데이터 들어보겠습니다.


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 100000

이 경우에, 이진 탐색 트리에 추가하기 위해서 노드 탐색을 몇 번이나 할까요?

chogahui05   2년 전

제가 들어드린 데이터로 이진 탐색 트리를 구축하면

1 (root) - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - ...

이런 식으로 편향되게 구축이 되게 되는데요. 자료 구조 시간에도 많이 배우셨겠지만.

이게 이진 탐색 트리의 단점입니다.


트리 같은 경우, 탐색 시 시간 복잡도도 굉장히 중요한 요소 중 하나인데요.

저렇게 구축되면 O(n)이겠죠. 링크드 리스트보다 더 나쁩니다. (공간도 포인터 형 크기만큼이나 더 크고) 


링크드 리스트는 head 포인터만 쭉 따라가면 되는데

이진 트리는 left, right 둘 다 비교해서 내려가야 하니까요. 복잡도는 같은데, 앞에 상수가 다르다고 할 수 있겠네요.


jre 8에서 부터는 HashMap이 레드 블랙 트리를 쓰게끔 만들어져 있는데요.

이전까지는 LinkedList를 사용했습니다. 같은 주소끼리 충돌이 났을 때.

이렇게 변한 게 무슨 큰 거냐고 생각하실지 모르겠지만요.


최악의 경우에 선형만큼 탐색해야 하는 것과

O(logn) 만큼 탐색하는 것과는 차이가 크겠지요?

댓글을 작성하려면 로그인해야 합니다.