아마도 수학적으로 트리가 무엇인지 개념을 알고 계신분들은 이 글을 보는데 전혀 지장이 없으리라 판단되는데, 그 트리가 이 트리이기 때문이다. 트리란, 이름 그대로 나무의 형상을 한 자료구조를 뜻하는데 그렇다고 정말 나무처럼 생겼느냐? 그건 아니지만, 일단 나무와 유사하다... 정도로 이해하고 넘어가면 될 것 같다.


위의 이미지는 바이너리 트리, 즉 이진 트리인데, 이미지는 위키에서 가져왔다.

이 트리 구조는 보기에는 굉장히 짜증나고 번거로운데, 생각보다 정말 많은 곳에서 사용하고 있다는 것이 중요하다. 어디에서 사용되는 지보다 이 트리를 확실하게 배워야 추후에 배울 탐색 트리에 대한 개념을 정확하게 이해하고 넘어갈 수 있기 때문에 중요한 것이라고 생각한다.

트리는 뿌리, 가지, 그리고 잎으로 구성이 된다. 뭐 어떻게 바라보면 실제 나무의 구성 요소와 크게 다르지 않다. 위의 이미지로 설명을 하자면 A, B, ..., I까지 각각은 하나의 노드로 부르고, 이들이 위치하는 곳에 따라서 이를 뿌리냐, 가지냐, 잎이냐로 구분을 한다. 또한 부모, 자식, 조상의 개념이 있는데 우선 뿌리, 가지, 잎을 우선적으로 설명을 하고 하도록 하겠다.

위의 이미지로 예를 들자면 뿌리는 F가 될 것이고, 가지는 B, D, G, I가 될 것이다. 잎은 A, C, E, H가 된다. 여기서 잎은 가장 최종적인 위치에 있는 것을 의미하기 때문에 Terminal이라고 불리기도 한다. A와 D는 서로 같은 부모인 B에서 나왔다. 따라서 이 둘은 서로 형제 관계이다. C와 E에게 D는 부모이고 F역시 조상이다.


위의 이미지에서 F와 B,G 사이에 선을 그어보자. (상상을 하길 바란다.) 또한 아래의 A, D, I와 B, G 사이에도 가로로 선을 그어보자. 이렇게 레벨을 나눌 수 있다.


또한 만약 B 노드에서 E 노드를 찾아간다면 D를 거쳐가게 된다. 'B, D, E'를 경로라고 이야기를 하고 B에서 E까지의 길이는 2가 된다. 여기에 자식의 개수를 이용하여 Degree라고 하는 용어가 있는데, 예를 들어 A의 Degree는 2이며, I의 Degree는 1이 된다. (어차피 이진 트리라서 2 이상이 나올 수 없다. -_-)

다음 글에서는 이진 트리에 대해 다루도록 하겠다.
저작자 표시 비영리 변경 금지
신고
by 가우초 2011.09.25 16:31
| 1 2 |

티스토리 툴바