자유 게시판 / Forum

BTS 알고리즘 질문

by kheedogg, 11월 22일, 21:02

BTS delete 함수 알고리즘 관련 질문드립니다.

Delete 함수 작성시, 중간노드를 지우는 작업에서 recursive 하게 삭제되는 과정이 구현되지 않은 코드가 점수가 더 높게 나오는 것 같습니다.

확인해주시면 감사하겠습니다.

kheedogg , 11월 23일, 12:33
 네! 알겠습니다. 감사합니다 조교님~ 
assist , 11월 23일, 12:05
 네 맞습니다. 제가 실수를 했네요... 댓글 내 예제는 550의 빈 자리에 우측 서브트리의 최소값인 555가 대체되어 550-(R)600-(L)555-(R)580-(L)560-(R)570이 맞습니다. 채점 데이터도 해당 규칙을 지키도록 되어있습니다. 기말 1주 반 전까지는 예시 코드 및 채점데이터를 공개할테니 그때 확인 후 이의제기 신청해주시면 경우에 따라 재채점하도록 하겠습니다. 다만 질문자님의 제출본에서 오답 처리가 된건 delete의 구현이 아닌 다른 부분에서 발생한 문제입니다. 
kheedogg , 11월 23일, 11:03
 원래 550이 있던 자리에 550 right의 가장 작은 값인 555로 채워져야 하는 것 아닌가요? 제가 잘못 이해한걸까요 
assist , 11월 23일, 10:29
 확인결과 데이터에는 문제가 없습니다. 
assist , 11월 23일, 10:23
 500->550 오타입니다 
kheedogg , 11월 23일, 08:37
 500 600 580 560 555 570은 어떻게 나오는 건가요...? 500을 제거했는데 500이 남아있을 수가 있나요? 
assist , 11월 23일, 03:04
 몇번 데이터에서 차이가 발생하나요? 세부 확인 후 처리 공지 전달드리겠습니다.

댓글에 달아주신 예제는 구현상 500 600 580 560 555 570이 맞습니다. (본 과제에서는 self-balancing이 없습니다.) 
kheedogg , 11월 22일, 21:12
 각 명령어가 들어올 때마다 Preorder 형식으로 이진탐색트리 구조를 출력하였을 때, 
+ 500
500
+ 600
500 600
+ 550
500 600 550
+ 580
500 600 550 580
+ 560
500 600 550 580 560
+ 555
500 600 550 580 560 555
+ 570
500 600 550 580 560 555 570
- 500
600 550 580 560 555 570
이 아닌,
550 600 555 580 560 570
이 맞는 결과 아닌가요?