한동안 데이터베이스 자료를 정리하느라 본 카테고리를 신경쓰지 못했군요. 이번에는 이진 트리에 대해서 자세하게 알아보도록 하겠습니다. 사실 전의 글에서 소개를 했던 이미지 역시 이진 트리이지만, 본래 소개를 해야했을 트리는 N개의 노드를 가지고 있을 트리를 보여드려야 했습니다. 다만, 그 트리의 이미지를 그릴 생각을 하거나 정확한 이미지의 출처를 찾기가 귀찮았던 제 탓이죠. -_-



* 바이너리 트리란?

바이너리 트리는 2개 이하의 노드를 가지는 트리를 의미합니다.


위의 이미지는 이전의 글에서 사용을 했던 이미지입니다.
이진 트리에 대해서 조금 더 깊게 들어가기에 앞서, 적어도 완전 이진 트리에 대해서 이야기를 하고 가야합니다. 우선 위의 이미지는 완전 이진 트리가 아닙니다. 이유는 G 노드 아래에 I 노드가 있지만, H 노드가 G 아래에 들어가지 않고, 다시 I 노드의 하위 노드로 위치하고 있습니다. G 노드 하위에 위치할 수 있지만, I 노드 하위에 위치함으로서 G 노드가 완전해지지 않게 되었습니다.
아래의 이미지를 보시죠.


위의 이미지는 http://sir.unl.edu/portal/bios/Binary-Heap.php 에서 가져온 이미지입니다.
위의 이미지는 완전 이진 트리입니다. 특정 요소로 인하여 불완전하다고 할 것이 없습니다. -_- 이진 트리 검색을 할 경우 완전한 모습의 배치가 굉장히 중요하기 때문에 다른 것은 몰라도 적어도 완전 이진 트리에 대해서는 알고 넘어가시는 것이 좋다고 판단합니다.



* 이진 트리 순회

순회의 종류는 아래의 3가지가 존재하며, 위의 이미지를 참고하면서 순회 순서를 확인하시기 바랍니다.

- 전위 순회(Preorder Traversal) : 100 - 19 - 17 - 2 - 7 - 3 - 36 - 25 - 1 (루트 노드를 시작으로 아래로 내려오면서, 좌측 하위 트리를 먼저 방문하고, 우측 하위 노드를 방문)
- 중위 순회(Inorder Traversal) : 2 - 17 - 7 - 19 - 3 - 100 - 25 - 36 - 1 (왼쪽 하위 트리부터 시작하여, 루트를 거쳐, 우측 하위트리를 방문)
- 후위 순회(Postorder Traversal) : 2 - 7 - 17 - 3 - 19 - 25 - 1 - 36 - 100 (왼쪽 하위 트리, 우측 하위 트리, 그리고 루트)


아래의 도서에서는 중위 순회를 이용하여 후위 표기식 연산기를 구현하는 것에 대한 내용이 있습니다.
알고리즘
카테고리 컴퓨터/IT > 컴퓨터공학
지은이 박상현 (한빛미디어, 2009년)
상세보기



* 바이너리 트리에서 노드의 추가와 삭제

뻔한 내용이라고 생각할 수 있지만 위키 자료를 참고하다가 아래의 이미지가 그래도 한번 짚고 넘어가는 것이 좋을 수 있겠다는 판단이 들어 설명을 하고 글을 마무리하겠습니다.
http://en.wikipedia.org/wiki/Binary_tree


위의 이미지는 이진 트리에서 하나의 노드를 삭제하는 과정을 설명하고 있습니다. 만약 좌측의 이미지에서 A 노드를 제거하고 싶다면, 우선 B와 D를 서로 연결을 한 뒤, A 노드를 삭제한다는 것입니다.


위의 이미지는 이진 트리에서 새로운 노드를 삽입하고자 할 때의 과정을 보여줍니다.


이진 트리에 대한 글은 여기서 마무리 합니다.
다음에는 정렬에 대한 내용을 진행하도록 하겠습니다. 트리에 대해서는 나중에 추가 보충이 필요하다고 판단될 경우 추가하도록 하겠습니다.
저작자 표시 비영리 변경 금지
신고

+ Recent posts