트리

트리란?

트리(tree)란? 트리라는 단어는 익숙할 것이다. 한국어로 나무라는 뜻이고, 프로그래밍에서는 자료구조의 명칭중 하나로 불린다. 우리는 프로그래밍에서의 트리를 알아볼 것이기 때문에 왜 이런 이름이 붙었는지 살펴보자.

트리라는 이름이 붙은 이유는 나무같이 생겨서이다. 그래서 노드끼리 서로 연결된 부분을 가지라고 부른다.

용어설명

루트
트리의 가장 윗부분에 위치하는 노드, 하나의 트리에는 하나의 루트만 존재한다.

리프
트리의 말단에 존재하는 노드, 해당 노드가 어느 레벨에 있는지 상관하지 않고, 더 이상 뻗어 나가지 않는 말단에 위치하면 해당 노드는 리프이다.

안쪽 노드
리프를 제외한 나머지 노드(루트 포함)를 안쪽 노드라고 한다.

자식
어떤 노드에서 가지로 연결된 아래쪽 노드를 자식(child)라고 한다. 노드는 자식을 여럿 가질수있으나, 부모는 한개이다.

부모
어떤 노드에서 가지로 연결된 바로 위쪽 노드를 부모(parent)라고 한다. 각 노드에서 부모는 하나 뿐이다. 위 예시 Y노드의 부모노드는 X이다.

형제
부모가 같은 노드를 형제(sibling)라고 한다. 위 예시에서 Y와 Z는 같은 부모X를 둔 형제노드 관계이다. (Z는 또한 리프)

조상
어떤 노드에서 위쪽으로 뻗어 나간 모든 노드를 조상이라고 한다.
노드A의 모든 조상으로 Y,X,루트가 있다. (A는 또한 리프)

자손 어떤 노드에서 아래쪽으로 뻗어 나간 모든 노드를 자손(descendant)라고 한다.

레벨 루트로부터 얼마나 떨어져 있는지를 나타낸 값을 레벨(level)이라고 한다. 루트의 레벨은 0이고, 루트에서 가지가 아래로 하나씩 뻗어나갈때 마다 레벨이 1씩 늘어난다. (마치 촌수와 같다)

차수
노드가 갖는 자식의 수를 차수(degree)라고 한다. 예를 들어서 X의 차수는 2, Y의 차수는 3이다. 모든 노드의 차수가 n 이하를 n진트리라고 한다. 자주사용하는 2진트리나 위 예시의 3진트리가 그것이다.

높이
루트에서 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)를 높이라고한다. 위 예시 트리의 높이는 3이다.

서브 트리
트리 안에서 한 부분을 칭한다. 루트는 한개이어야 하기에 루트의 형제를 한 서브트리에 둘 수는 없다. 어떤 노드를 정하고 그 자손으로 이루어진 트리를 서브트리(subtree)라고 한다.

널 트리
노드가 전혀 없는 트리를 널 트리(null tree)라고 한다.

순서 트리와 무순서 트리

형제 노드 사이의 순서 관계를 따지는지, 안따지는지에 따라 트리를 두 종류로 분류한다. 형제 노드의 순서를 따지면 '순서 트리(ordered tree)', 그렇지 않으면 '무순서 트리(unordered tree)'라고 한다.

위 그림에서 a,b는 순서 트리로서는 다른 트리이지만, 무순서 트리로서는 같은 트리가 된다.