[260612]트리의 기초

목차

• 트리의 개념 및 용어
• 이진트리

트리의 개념 및 용어

트리의 개념

트리(Tree)는 부모와 자식관계로 데이터를 저장하는 계층형 자료구조이다.
트리라는 이름에 맞게, 나무가 뿌리를 뻗어나가는 구조와 같다.

트리의 특징

트리는 노드와 간선으로 이루어져 있다. 노드는 변수 간선은 변수끼리 이어주는 선이라고 생각하면 편하다.

• 트리의 기본 특징
  트리는 부모-자식관계로 데이터가 포함된다.
  모든 노드는 서로 연결되어 있다.
  순환 구조 즉, 사이클이 없다. 모든 노드는 각 노드끼리 순환되지 않는다.

• 계층 간 분류
  트리는 부모노드와 자식노드 형제노드가 있다.
  부모 노드: 연결된 두 노드중 상단에 위치한 노드.
  자식 노드: 연결된 두 노드중 하단에 위치한 노드.
  형제 노드: 같은 부모를 공유하는 노드.

• 노드 간 분류
  루트 노드: 트리의 최상단에 있는 노드. 부모가 없다.
  리프 노드: 트리의 최하단에 있는 노드. 자식이 없다.
  내부 노드: 적어도 하나의 자식이 있는 노드. 루트 노드 또한 내부노드이다.

그 외 트리의 용어

깊이(Depth)

• 주로 머신러닝, 딥러닝에서 자주 사용하는 개념이다. 루트 노드에서 특정 노드까지의 간선 수를 의미하며, 루트의 깊이는 0 한칸씩 내려갈떄마다 1이 증가한다.

레벨(Level)

• 같은 깊이를 가진 노드의 집합. 형제노드 또한 같은 레벨이라 할 수 있다.

높이(Height)

• 트리의 최대 깊이를 의미한다. 루트 노드부터 가장 먼 리프 노드까지의 간선 수, 즉 트리의 최대 길이를 의미한다.

차수(Degree)

• 자식이 몇명인지를 의미한다. 트리 전체의 차수를 구할때는, 가장 큰 차수를 구하면 된다.

서브트리(Subtree)

• 트리 내의 트리이다. 하나의 노드와 그 노드의 자식들로 이루어져 있다.

경로(Path)

• 한 노드에서 다른 노드로 가는 길. 경로의 길이는 한 노드에서 다른 노드로 갈때 거쳐가는 간선의 수를 의미한다.

이진트리

이진트리의 개념

이진트리는 간단하다.
트리중 최대 2명의 자식노드를 가지는 트리 구조를 이진트리라고 부른다.
자식이 없거나, 1개만 있거나, 2개 모두 있을 수 있으며, 각 노드는 왼쪽자식과 오른쪽 자식으로 분류된다.
여러가지 이진트리가 있는데, 특히 모든 노드가 2개의 자식을 가지는 트리를 완전이진트리라고 부른다. 힙과 우선순위 큐 구현에서 완전이진트리를 사용함으로 무조건 알아야하는 기초적인 지식이다.