 |
| By Matt Swalm/flickr |
내용은 내가 언급한 Full Binary Tree와 Complete Binary Tree의 설명이 뒤바뀌었다는 것이다. 실제 위키피디아 등의 자료를 찾아보니 내가 틀린게 확실했다. 올바른 지적이었고, 그래서 그분께 고마움을 전하고 싶다.
늦었지만 잘못 되었던 내용을 바로잡고자 AS 성격의 이 글을 쓴다. 잘못된 내용이 있는 그 장도 최대한 오류를 수정했다. 다만 동영상의 내용은 기술적으로 어려움이 있어 어떻게 할까 고민 중이다.
사람에게 어떤 지식 체계가 한번 주입되어 자기것이 되고 나면, 그것이 틀렸다고 의심하기 참 어렵다. 그래서 변화가 어렵고, 시니어가 버티기 어려운 세상이다.
Full Binary Tree와 Complete Binary Tree에 대해 왜 잘못 알고 있었을까? 고민해 보았지만, 별다른 이유를 찾지 못했다. 다만 Robert Sedgewick 교수가 쓴 원서로 처음 이진트리에 대해 공부했기에, 영어 문장을 잘못 해석해 이해하지 않았을까 생각된다. 당시에는 제대로 된 한글 알고리즘 책이 없었기 때문에 빚어진 해프닝인 것 같다.
그럼 위키피디아를 기반으로 해서 이진트리의 종류에 대해서 정리해 보겠다.
먼저 Full Binary Tree(정 이진트리)는 트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우이다. 즉 자식을 하나만 가진 노드가 없어야 한다. 그래서 다음 그림의 트리는 Full Binary Tree가 된다.
 |
| From Wikipedia / Full Binary Tree |
마지막으로 Perfect Binary Tree(포화 이진트리) 모든 레벨에서 노드가 꽉 차있는 트리를 의미한다. 즉 Perfect Binary Tree는 Complete이면서 Full인 이진트리이다.
이 중에서 힙(Heap) 정렬에서 쓰이는 트리는 Complete Binary Tree 즉 완전 이진트리이다.
한편 위키피디아에서도 언급하지만, 어떤 사람들은 Perfect Binary Tree의 정의를 Complete Binary Tree라고 언급하고, Complete Binary Tree의 정의는 Almost Complete 혹은 Nearly Complete Binary Tree라고 언급하기도 한다. 하지만 앞서의 정의가 거의 정설이 된 것 같다.
여담
앞서 언급했듯, 나는 알고리즘을 Robert Sedgewick 교수의 Algorithms in C의 초판 원서를 보고 주로 공부했다. 물론 다른 여러책을 보기도 했지만, 가장 큰 줄기는 바로 이 책을 통해 세우게 되었다.
그런데 1990년에 출간된 이 책의 Binary Tree 설명을 보면 모호하기 짝이 없다.
Full Binary Tree는 마지막 레벨을 제외한 윗쪽 레벨의 모든 노드가 채워져 있는 것으로 정의했고, Complete Binary Tree는 Full Binary Tree이면서 마지막 레벨의 노드가 왼쪽으로 몰아 놓은 것으로 정의했다. Complete Binary Tree는 지금의 정의와 동일하나, Full Binary Tree는 완전히 다르다. 게다가 당시 나를 더 헷갈리게 했던 것은 Figure 4.3의 그림이었다. Complete Binary Tree라고 예시를 들었지만 전혀 정의와 맞지 않다.
어떤 형태의 것을 정리하고 이름을 붙이는 것이 다 이럴 것이다. 처음에는 각자의 의견이 다양하게 존재하겠지만, 논의를 통해 정리되고 하나로 통일될 것이다. 하지만 일부 다른 의견 혹은 옛 의견들이 문서로 남아 새로 공부하는 사람들을 헷갈리게 할 것이다.
그런 면에서 집단 지성으로 정리해놓는 위키피디아가 이런 모호함을 정리하는 기준점이 되어주고 있어 다행이다.
아무쪼록 인터넷도 없던 어린 시절, 딸리는 영어 실력으로 공부하느라 머리에 쥐가 났고 그래서 멘붕에 빠졌던 나를 이해해 줬으면 좋겠다.
댓글 없음:
댓글 쓰기