playsworld16   1년 전

transformation중에 3번 과정을 보면

3. Insert node $x$ back into the tree, between $y$ and the descendant of $y$ from whose subtree $x$ was removed.

2에서 제거한 x를 (y, x가 제거된 y의 후손) 사이에 넣으라고 되어있는데, 해당 조건을 만족하는 y의 후손이 여럿인 경우 어디에 들어가야할지 정해지지 않습니다.

descendant(후손)이 아니라 child(자식) 이라고 바꾸면 x가 들어가야할 자리가 항상 유일하게 결정되고, 이렇게 해야 정답을 맞출 수 있습니다.

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