본문 바로가기

(탈퇴) 테슬라's Post

이진 트리(Binary Tree) - 트리란?

안녕하세요~
네 잊을만 하면 나타나는 테슬라입니다.
이번 시리즈는 이진트리에 대해서 다루어보겠습니다.
음 오늘은 간단하게 트리에 대해서 다루어 보겠습니다.
음 트리란 무엇인가... 우선 트리하면 크리스마스 트리가 떠오르지요? (크리스마스가 얼마 안 남아서요...ㅎㅎ)
네 트리하면 나무지요...네 맞아요...
음 자료구조의 트리도 나무와 비슷합니다.
루트라는 뿌리를 기점으로 가지가 뻗어나가고 끝에는 잎들이 달려있죠...

사용자 삽입 이미지


음 나무를 뒤집어 나뒀다고 해야 할 것 같군요.
맨 처음엔 뿌리(root)가 존재하고, 그곳에서 가지(branch)가 존재하며, 결국 끝에는 잎(leaf)가 붙어있습니다.
루트는 제일 상위레벨에 속하는 노드로써 그냥 맨처음에 시작하는 부분을 말합니다.
가지 즉 간선은 노드와 노드 사이를 연결하는 선들을 말합니다. 따라서 노드가 n개라면 간선은 n-1이지요
잎 그러니까 리프는 맨끝 밑에 아무런 가지가 안달려있으면 리프라고 합니다.
음 또한 트리에는 단어가 많습니다. 아 단어보다 먼저 트리의 정의를 알아봐야겠군요.


트리는 하나이상의 노드로 구성된 유한 집합으로 루트라는 특별한 노드가 있고, 나머지 노드들도 서로 교차하지 않고 분할될 수 있는거지요. 분할 되면 부트리(Subtree)라고 합니다. 노드A는 루트이고 만약 위에 그림을 분할 시키면 {B,D}와 {C,E,F} 두개의 집합으로 나눌 수 있겠죠?
위에 그림은 트리의 구조라고 할 수있습니다.
그럼 아래 그림을 보죠
사용자 삽입 이미지

위 그림은 트리가 아닙니다.
왤까요? 네 그렇습니다. 화살표가 맨 밑에 중간 노드에 2개가 가지요?
예 이런식으로 교차가 되면 트리라고 부를 수 없습니다.
왜냐하면 이런식으로 교차하면 부수적으로 분할 시킬수 없기 때문이지요.


이제 트리 정의 부분은 넘어가고, 단어 정의를 해볼까요?
우선적으로 부모 노드(Parent Node)와 자식 노드(Child Node)가 있습니다.
자식 노드는 부모 노드에서 내려온 노드를 뜻합니다.
음 간단하게 부모님에게서 자식들이 태어나듯이 말입니다.
위 그림에서 예를 들어본다면 노드C의 경우 부모노드는 무엇일까요? 네 간단하게도 노드A입니다.
음 그럼 자식 노드는 어떨까요? 네 그렇습니다. 노드E와 노드F입니다.
그냥 단순하게 생각하시면 됩니다.

형제 노드(Sibling Node)는 같은 부모노드에서 내려온 노드를 뜻합니다.
아까 노드C의 부모노드가 노드A였으므로 노드C의 형제노드는 노드B가 되는 것이지요.

조상 노드(Ancestor Node)와 후손 노드(Descendant Nose)라는 것들도 있습니다.
조상 노드는 루트까지 갈때 거치는 노드들입니다.
이번엔 노드F를 예로 들어보죠. 노드F에서 루트인 노드A까지 가려면 노드C와 노드A를 거치지요.
네 이 노드들이 조상노드입니다.
후손노드는 반대로 그 노드에서 끝까지 내려가는 노드입니다.
노드A의 후손노드들은 노드B,C,D,E,F군요

음 차수(Degree)란 말도 있군요
간단하게 설명하면 자신에 연결된 자식노드의 갯수라는 말로 할 수 있겠군요.
노드B의 차수는 1, 노드C의 차수는 2, 노드F의 차수는 0이군요.
트리의 차수는 각 노드들중에서 최대치를 트리의 차수라고 합니다.
위 그림에선 차수2가 가장 크므로 차수2인 트리라고 할수 있습니다.

마지막으로 레벨(Level)이 있습니다.
레벨은 루트를 최상위 레벨인 1로 하고,레벨 N의 자식노드는 N+1레벨입니다.
즉, 루트로부터 차근차근 레벨이 커지는 거지요.
노드F의 레벨은 몇일까요?
노드A은 레벨1, 노드C는 레벨2, 그리고 노드F는 레벨3이 되는것이지요.


음 우선 트리와 단어를 정리해봤는데요...으으 정신이 없군요....
다음 포스트는 이진트리에 대해 쓰도록 하겠습니다.