[구자민]

추석 때 고향갈 예쩡이라 일찍도 PL 숙제를 하는 불쌍한 수강생입니다.. exercise 1,2에서 애매한 것이 있어서 질문을 드립니다.

1. '일반적으로' 게임 대진표는 complete binary tree라는 설명이 있습니다. 그렇다면, 이번 tournament도 모두 complete binary tree라고 가정해야만 하나요?

2. 만약 그렇다면, exercise 2에서 1개의 팀을 삭제했을 때 대진표의 작성방법이 다양해집니다.
만약 항상 complete binary tree의 성질을 만족시키지 않아도 된다면 직관적으로 대진표를 수정하는 것이 가능합니다.
하지만, 항상 complete binary tree의 성질을 만족시키려면 주어진 팀들의 위치를 shift시키거나, 맨 끝에 있는 team을 빼서 빠진 team의 자리에 집어넣는 등의 작업을 통해 항상 complete binary tree의 성질을 만족시키도록 해야 한다고 생각합니다. 아니면 avl tree와 유사하게 회전을 시키던지요.
제가 생각하는 것 외에 '일반적으로 leaf가 빠졌을 때 complete binary tree의 성질을 유지시키도록 하는 방법'이 있으면 알려주시구요. 그렇지 않다면 어떤 기준을 통해 complete binary tree의 성질을 맞춰야 할지가 궁금합니다.

사실 제 생각에는 이번 게임 대진표는 보통 binary tree로 짜는 것이 좋을 거라 생각합니다. 일반적인 게임 대진표는 complete binary tree이긴 하지만, 이는 대진표를 짠 뒤에 대진표가 변경되지 않는다는 것을 전제로 하는 것이니까요.

좋은 답변 부탁드립니다.^^

[정영범]