3. Tree

Tree

Tree의 기본적인 정의는 Circuit이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 Graph를 말한다.

따라서 Tree는 Graph의 종류 중 하나이며 다음과 같은 특징을 갖는다.

 

Parent, Child

연결 리스트의 경우 다음 노드 하나를 가리키지만 Tree의 경우 여러 개의 노드를 가리킬 수 있다.

이렇게 가리켜진 노드들을 child 노드라고 하며 가리킨 노드를 parent 노드라고 한다.

 

예를 들어 4번, 5번 노드는 2번의 child이고, 2번 노드는 4번, 5번 노드의 parent이다.

동시에 5번 노드는 8번 노드의 parent이고, 2번 노드는 0번 노드의 child이다.

이처럼 parent, child 노드는 상대적인 개념이다.

 

이에 더해 ancestor는 해당 노드의 부모, 부모의 부모 등 위의 모든 노드를 나타내고,

descendant는 해당 노드의 자식, 자식의 자식 등 아래 모든 노드를 나타낸다.

 

Root, Leaf

이렇게 부모 자식 관계에서 가장 위의 노드(부모가 없는 노드)를 root 노드라고 하며,

가장 아래의 노드들(자식이 없는 노드)을 leaf 노드라고 한다.

따라서 위 트리에서 root 노드는 0번 노드이며, leaf 노드는 6, 7, 4, 8번 노드이다.

 

또한 자식을 하나 이상 가진 노드를 internal 노드, 자식이 없는 노드를 external 노드(=leaf 노드)라고도 한다.

위 트리에서 internal 노드는 0, 1, 2, 3, 5번 노드이며, external 노드는 6, 7, 4, 8번 노드이다.

 

Depth, Height

노드의 depth란 해당 노드가 갖는 parent 노드의 수를 나타낸다.

따라서 root 노드의 depth는 0이며, 각 노드의 depth는 parent 노드의 depth + 1 이 된다.

 

노드의 height는 해당 노드로부터 자손 leaf 노드까지의 최대 거리를 나타낸다.

따라서 leaf 노드의 height는 0이며, 각 노드의 height는 child 노드의 height 중 최댓값 + 1 이 된다.