[EKOO의 JAVA를 이용한 자료구조:7회] Tree (1)

[EKOO의 JAVA를 이용한 자료구조:7회] Tree (1)

저자:EKOO| 날짜: 2005년 05월 04일

 

참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며...

안녕하세요. 이번 강좌에서는 Tree를 배워보게 됩니다. 윈도우 탐색기를 한번 실행시켜 보시겠어요? 왼쪽에 보시면 바탕화면, 내문서, 내 컴퓨터 등의 아이콘이 보이실겁니다. 그 옆에는 +, - 기호들도 보이시죠? 그 기호 옆에는 폴더가 보이게 되죠. 이것이 바로 Tree입니다. 이 이름은 실제로 Tree구조의 형태가 나무를 뒤집어 놓은듯한 모양이라고 해서 그렇게 지었다고 합니다.

실제로 자료구조에서도 많이 개념을 사용하구 있구요, Algorithm 에서도 많이 Tree의 개념을 사용하고 있습니다. 유명한 0-1 Knapsack알고리즘이나, n-queens 알고리즘에서도 트리구조를 이용하여 Solution 을 구해내는 것을 경험해 보신 독자분들도 있으리라 생각됩니다. 그럼 이제부터 Tree의 세계로 여행을 떠나볼까요?

Tree란?

Tree란 말 그대로 나무입니다. 이 나무를 거꾸로 매달아놓은 형태가 바로 Tree 구조의 기본이죠.

[그림1] Tree구조

위에 보시는 형태가 바로 트리입니다. [그림1]의 오른쪽 그림은 나무 그림을 뒤집어 넣은 그림입니다. 나무에는 가지가 있죠? 이 가지를 Tree구조에서는 Node라고 하며, [그림1]의 왼쪽 그림에서의 네모를 Node라고 부릅니다. 나무는 가지가 하늘을 향해서 뻗치죠? Tree는 나무를 뒤집어 놓은 형태기 때문에 Node들이 아래를 향해서 뻗쳐지게 됩니다.

독자여러분. 나무에서 가장 중요한게 뭘까요? 잎? 꽃? 열매? 물론 생각하신것들도 다 중요하지만, 나무는 뿌리가 없으면 안되죠? 뿌리가 있어야 어린나무가 자라서 큰 나무가 되죠. Tree구조에서도 역시 뿌리가 가장 중요합니다. 이를 Root 라고 부릅니다. [그림1]에서 맨 위에 있는 Node가 Root Node가 됩니다. 앞서의 Linked list 에서는 Head Node로 어떤 Node라도 찾아갈 수 있었듯이, Tree에서도 Root만 잃지 않고 있다면 어느 Node라도 방문하여, 삽입, 삭제, 수정등의 작업을 하실 수 있습니다.

이정도라면 Tree에 대한 간단한 소개가 되었겠죠? 이제 이런 Tree를 이용하여, 구체적으로 어떻게 Tree의 개념을 사용하는지에 대하여 알아보도록 하겠습니다.

Tree의 중요 용어

[그림2]Tree에 쓰이는 용어

독자분들께서 이해하시 쉬우시도록 번호가 붙은 Node들을 가지고 있는 Tree그림을 예로 용어를 설명하겠습니다.

Level	Node 2,3의 Level은 2입니다. root에서부터 자신까지 오는데 거치는 Node의 갯수라고 할 수 있습니다.
Parent	Node 2는 Node 4,5의 Parent 입니다. 자신과 위로 연결되어 있는 Node를 Parent라고 합니다.
Children	Node 4,5는 Node 2의 Children 입니다. 자신과 아래로 연결되어 있는 Node를 Children이라고 합니다.
Leaf	자식이 없는 Node들을 가리킵니다.
Sibling	같은 부모를 가진 Node들을 Sibling이라고 합니다.
SubTree	Node 2를 root로 하는 Tree는 Node 1을 root로 하는 Tree의 SubTree라고 합니다. Node 3을 root로 하는 Tree도 SubTree라고 할 수 있겠죠.