트리(tree)

in Blog / 알고리즘

트리란, 나무 모양과 비슷하다고 하여서 이름이 붙여졌다.

나무

트리 용어에 대해 설명할게

트리 용어

트리용어

  • 노드와 가지로 구성되며, 가장 위쪽에 있는 노드를 루트(root) / 가장 아래쪽에 있는 노드를 리프(leaf)

  • 비단말 노드(Internal node) : 리프를 제외한 노드, 내부 노드라고도 함

  • 노드 가지 위쪽의 노드는 부모 / 노드 가지 아래쪽의 노드는 자식

  • 부모가 같은 노드를 형제

  • 어떤 노드에서 위쪽으로 가지를 따라가며 부모보다 높은 노드를 조상이라고 함

  • 어떤 노드에서 아래쪽으로 가지를 따라가며 자식보다 낮은 노드는 자손

  • 레벨이란, 가장 위쪽부터 0으로 시작하고 하나씩 내려갈때마다 1씩 증가

  • 자식의 수를 차수라고 하며, 모든 노드의 차수가 n이하인 트리를 n진 트리라고 함

  • 높이 : 루트에서 가장 멀리 있는 리프까지의 거리

  • 서브트리 : 특정 노드를 루트로 잡고 새롭게 볼때 이런 용어를 씀

  • 노드와 가지가 전혀 없는 트리를 빈 트리(None tree) 또는 널 트리(null tree) 라고 함

순서 트리와 무순서 트리

형제 노드의 순서 관계가 있는지에 따라, 순서 관계가 있으면 순서 트리(ordered tree), 구별하지 않으면 무순서 트리(unordered tree)라고 함.

다른 트리에서 보았을때, 순서 트리로 보면 같지 않지만, 무순서 트리로 보면 같을 수 있다.

순서 트리의 검색

2가지로 나뉘게 되는데, 아래와 같다

폭 우선/가로 우선/수평 검색이라고 하며, 낮은 레벨부터 왼쪽에서 오른쪽으로 검색한다.

세로/수직 검색이라고 하며, 리프에 도달할 때까지 아래쪽으로 내려가면서 검색, 리프에 도달하면 부모에 다시 돌아가 다시 또 내려간다.

깊이 우선 검색은 세 종류의 스캔 방법이 있는데, 아래와 같다

  • 전위 순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

  • 중위 순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

  • 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

© 2022 JeongHwan Yun.