예전 자유 게시판

게임 프로그래머를 위한 자료구조와 알고리즘 문의

원치훈 2009-11-03 16:11

안녕하세요 책을 읽다가 햇갈리는 부분이 있어서 문의드립니다. 페이지 681쪽에 보면 단순 배열을 힙으로 변환하는 간단한 알고리즘의 4단계가 나오는데요, 첫 번째 단계가

1. 힙의 밑에서 두 번째 수준의 가장 큰 값에 해당하는 색인을 찾는다.

라고 되어 있는데, 뒤에 이어 지는 소스와 설명에서는 값을 참조해서 시작할 위치를 잡는게 아니라, 아래서 두번째 레벨의 (자식이 있는) 맨 오른쪽 노드에서 시작합니다. 어찌 구한 원서를 대조해보니

1. Find the last index on the second-lowest level of the heap.

이라고 되어 있네요, 가장 큰 값의 노드가 아니라, 맨 오른쪽 노드에 해당하는 노드의 인덱스를 구한다가 맞는 것 같아서 문의 드립니다. 682 페이지의 첫 줄도 그런 맥락에서 같은 문제가 있는 것 같습니다.

686쪽에 실제 소스 구현을보면 트리의 조밀성이 유지 된다는 가정하에 맨 마지막 층의 맨 마지막 노드의 부모 노드를 시작 노드로 삼고 있는 것 같습니다. 즉 밑에서 두번째 차원에 속한 최오른쪽 노드라도 자식 노드가 없으면 자식 있는 왼쪽 노드가 선택되는 구조더군요.(전체 노드수 / 2로 시작 노드 인덱스를 구하니까 그렇게 되더군요).

정리하자면

1.조밀한 트리의 밑에서 두번째 수준의 노드 중 (자식이 있는) 가장 오른쪽 노드의 색인을 찾는다. 네요.

설명이랑 소스가 잘 매치가 안되는 부분 같아서 끄적거려 봅니다. 좋은 하루 되세요 ^^