과연 40000개의 인덱스가 충분할까요? 평범한 이진 탐색 트리의 치명적인 약점이 바로, 트리의 균형이 크게 나빠질 수 있다는 것입니다.
아래처럼 하나씩 넣다보면 금방 터지는 순간이 나옵니다.
5639번 - 이진 검색 트리
djm03178님 말대로 이진 탐색 트리를 배열로 구현하면 최대 높이가 (노드 개수)-1 = 9999개이기 때문에 배열 크기가 2^10000-1이 되어야 합니다.
따라서 이 문제를 풀려면 연결 리스트처럼 노드 구조체를 만들거나, 이진 탐색 트리의 성질을 써서 트리를 만들지 않고 전위 순회에서 후위 순회를 바로 알아내어야 합니다.
댓글을 작성하려면 로그인해야 합니다.
dudgh623 5년 전
힙을 구현하는것 처럼
1부터 시작해서 현재 위치의 값보다 작다면 *2, 크다면 *2+1 하면서 배열에 집어넣었습니다.
배열초기값이 0이므로, tree[]의 값이 0일경우 그 위치에 입력받았던 값을 집어넣었습니다.
디버깅을 해봐도 생각한대로, 배열에 값이 다 들어갔습니다.
그 이후 순회해서 출력하도록했습니다.
현재 위치의 왼쪽과 오른쪽을 보면서 양 쪽모두 없으면 출력하는 방식으로 구현하였습니다.
배열크기도 더 늘려보기도, 줄여보기도 했는데 어느 부분에서 런타임 에러가 나는지 모르겠습니다...