인프런 커뮤니티 질문&답변
작성한 질문수
Disjoint Set 질문있습니다
작성
·
313
0
위 코드의 전체적인 구조를 보면
2
3__ 1
____10
이고
여기서 만약 Find(10)을 실행한다면
이 코드에 의해
2
3 1 10
이렇게 구조가 바뀔 텐데
_rank[2]의 값이 3에서 바뀌지 않는데
_rank 수정 코드도 필요하지 않나요?
답변 1
4
도움이 될 진 모르지만 저도 이 질문 보고 거의 일주일 넘게 답을 찾아 헤매서.. 지나가다 궁금해 하시는 분 계실까봐 댓글 답니다.
위키에 이렇게 적혀있네요.
While the rank of a node is clearly related to its height, storing ranks is more efficient than storing heights. The height of a node can change during a
Findoperation, so storing ranks avoids the extra effort of keeping the height correct.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank
해석하면
노드의 순위는 그 높이와 분명히 관련이 있지만, 순위를 저장하는 것이 높이를 저장하는 것보다 더 효율적이다. 찾기 작업 중에 노드의 높이가 변경될 수 있으므로 순위를 저장하면 높이를 정확하게 유지할 필요가 없습니다.
그래서 곰곰히 생각해 본 결과 find 연산 시 최적화를 위해 경로 압축 방법을 사용하고, union 연산 시 최적화를 위해 union by rank 방법을 사용하기 때문에 서로 다른 범위?라고 생각하는 게 전 제일 마음이 편했습니다..
한 번 매겨진 랭크는 증가만 할 뿐 딱히 감소하는 건 아닌 것 같네요. 랭크가 높을수록 union 연산을 많이 했다는 증거니, 아무래도 많은 쪽에 붙이는 게 확률적으로 이득이라 by rank나 by size 도 그런 비슷한 원리에서 나온 방법들 같다고 혼자 결론지었습니다..
저도 정확히 알고 싶은데.. 아직도 너무나 궁금합니다..ㅠㅠㅠ 혹시 정확히 알고 계신 분이 있으시다면 언제라도 좋으니 시원하게 알려주시면 감사하겠습니다.
(- -)(_ _)