[공순호]

fun rank EMPTY = 0
| rank NODE(r, _, _, _) = r

로 되어있는데요.


rank EMPTY = 0이면

shake( anyinteger, EMPTY, EMPTY) 하면

NODE(1, anyinteger, EMPTY, EMPTY)가 되어서, 왼쏠힙의 정의에 부합하지 않고

이런 경우가 일어나지 않는 것을 merge를 통해서 하려면 함수가 복잡하게 될 것 같은데요.


fun rank EMPTY = -1 로 하면 shake에서 rank를 이용할 때 모든 경우에 대해

올바르게 작동하고 따라서 merge에서 생각해줘야할 부분이 상대적으로 줄어들게 되는 것으로 보이는데, 제가 옳게 생각하는 것인지 궁금합니다.

[김덕환]

[윤상필]

저도 이부분 좀 이상하게 생각했었는데요.
스펙에 의하면 shake(1, EMPTY, EMPTY) 는 급수 1인 노드가 나오고 insert(1, EMPTY) 은 급수 0인 노드가 나옵니다.
보통 이 두개가 일치할 것을 기대하는 게 정상 아닌가요?
저 같은 경우는 EMPTY의 랭크를 -1로 하기 보다는 insert의 정의를
fun insert(x, h) = merge(h, NODE(1, x, EMPTY, EMPTY)) 이렇게 바꿔 가지고 해결했습니다.
상식적으로도 EMPTY 노드와 자식이 없는 노드의 급수가 같다면 왼쪽 자식이 EMPTY 이고 오른쪽 자식이 자식없는 노드인 경우에도 왼쏠힙의 정의를 만족한다고 볼 수 있으므로 모순이지 않나요? EMPTY와 자식없는 NODE는 급수의 차이가 1이어야 할 것 같습니다.

[김덕환]

[손님]

[김덕환]

[윤상필]

[김덕환]

[이기석]

저도 같은 문제로 고민하다가 이곳의 질문과 답변들을 보게됐습니다.

제 생각이지만 위의 문제를 merge 함수에서 패턴매칭 시키기 보다는

shake 함수에서 패턴매칭시키는 편이 훨씬 깔끔하게 해결 될것 같은데

shake 함수에 EMPTY가 인자로 들어올 경우를 처리할 수 있도록 패턴매칭을

추가시켜도 됩니까?


EMPTY 의 경우 NODE가 아니므로 rank의 정의에 의해 EMPTY에 대한 rank

를 따지는 것은 의미가 없다고 봅니다. 그래서 (rank EMPTY)의 값이 0이든 -1이

든 상관없다는 데에는 동의합니다. 하지만 shake 함수에서는 EMPTY를 rank가

0인 NODE와 동일시 하기때문에 NODE와 EMPTY의 rank를 비교하는 정의되지

않는 행동을 합니다. (EMPTY의 rank를 정의할 수 없다면 NODE와 EMPTY의

rank를 비교하는것도 정의할 수 없다고 생각합니다) 그렇기 떄문에 shake

함수에 인자로 EMPTY를 받아들일 경우의 패턴매칭을 추가시켜도 된다고 생각

하는데 어떨지 조교님께 여쭙습니다 ^^;

[손님]

[김덕환]

[김덕환]

[김덕환]

등교 버스가 늦게 오는 바람에 세 가지 정의가 다 개념 상 문제가 없는지 검토해보는 시간을 가졌습니다.

NODE (_, x, EMPTY, EMPTY)에 대해 deleteMin 함수를 호출했을 경우 아래처럼 될 겁니다.