주니어 백엔드 개발자 인터뷰

# 트리 (Tree)

정의

트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리구조로 배열된 일종의 계층적 데이터의 집합입니다.

image

  • 트리로 이루어진 집합을 숲이라고 합니다.
  • 일반 배열에서 삽입이나 삭제를 하는데 O(N)의 시간이 걸리며 배열의 첫번째 원소에 삽입하는 경우 나머지 모든 요소들을 한 칸씩 뒤로 미뤄야 하므로 최악의 시간 복잡도 O(N)이 나옵니다.
  • 하지만, 트리는 편향 트리가 아닌 이상 일반적인 트리에서는 O(log N) 정도의 시간으로 줄여집니다.

# 트리의 주요 구성

  • 루트 노드, 내부 노드, 리프 노드 등으로 구성됩니다.
  • 루트 노드(root node) : 가장 우위에 있는 노드를 뜻하며, 0개 이상의 자식 노드를 가지고 있습니다. 보통의 트리 탐색 문제에서 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경향이 있습니다.
  • 내부 노드(internal node) : 루트와 리프를 제외한 노드로, 다른 용어로 끝이 아닌 노드(non-terminal node)라고 합니다.
  • 단말 노드(leaf node) : 트리의 가장 아랫부분에 위치하는 노드로, 더 이상 뻗어나갈 수 없는 마지막에 위치한 노드입니다.

# 트리의 용어들

  • 부모 노드(Parent Node) : 어떤 노드에서 간선으로 연결된 위쪽 노드로, 노드는 1개의 부모를 가진다. 예를 들어 Y의 부모는 X입니다.
  • 형제 노드(Sibling Node) : 같은 부모를 가지는 노드입니다.
  • 조상 : 어떤 노드에서 간선으로 연결된 위쪽 노드 모두를 말합니다.
  • 자손 : 어떤 노드에서 간선으로 연결된 아래쪽 노드 모두를 말합니다.
  • 노드의 레벨(level) : 루트로부터 얼마나 떨어져 있는지에 대한 값입니다. 루트의 레벨은 0이고 루트로부터 간선이 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어납니다.
  • 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수. 예를 들어 X의 크기는 4입니다.
  • 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말한다. 예를 들어 Y의 깊이는 2입니다.
  • 트리의 차수(degree of tree) : 노드가 갖는 자식의 수를 말하며, 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 합니다. 예를 들어 그림은 모든 노드의 자식이 3개 이하이므로 3진 트리입니다.
  • 트리의 높이(height) : 루트로부터 가장 멀리 떨어진 리프까지의 거리를 말합니다.
  • 서브 트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 말합니다.

# 이진 트리 (BinaryTree)

정의

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리(Binary Tree)라고 합니다.

image

  • 이진 트리는 노드가 왼쪽 자식과 오른쪽 자식을 가지며, 각 노드의 자식은 2명 이하만 유지해야 합니다.
  • 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있습니다.
  • 일반 트리와는 달리 이진 트리는 서브 트리 간에 순서가 존재합니다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리를 구별합니다.

# 이진 트리의 종류

image

# 정이진 트리 (Full Binary Tree)

정의

자식 노드가 0또는 두개인 이진 트리

  • 각 내부 노드가 두 개의 자식 노드를 갖는 순서화된 트리입니다. (홀수 개의 자식 노드를 가질 수 없습니다.)

# 완전 이진 트리 (Complete Binary Tree)

정의

왼쪽에서부터 채워져있는 이진 트리.

  • 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.

# 포화 이진 트리 (Perfect Binary Tree & Full and Complete Binary Tree)

정의

모든 노드가 꽉 차있는 이진트리

  • 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 이진 트리를 의미합니다.

# 균형 이진 트리 (Balanced Binary Tree)

정의

왼쪽과 오른쪽 노드의 높이 차가 1 이하인 이진트리

  • map, set을 구성하는 레드 블랙 트리를 균형 이진 트리 중 하나입니다.

# 자바에서의 트리

# TreeSet

image

  • 이진 트리를 기반으로한 Set Collection입니다.
  • TreeSet에 객체를 저장하면 자동으로 정렬되는데 이진탐색트리처럼 부모 노드값과 비교해 낮으면 왼쪽 자식노드, 높으면 오른쪽 자식 노드에 저장합니다.
// TreeSet 생성하기
TreeSet<Integer> scores = new TreeSet<Integer>();

// 값을 삽입하기
scores.add(new Integer(87));

// 가장 상위의 값을 가져오기
scores.pollFirst();

// 가장 하위의 값을 가져오기
scores.polLast();

# TreeMap

image

  • TreeMap은 이진 트리를 기반으로 한 Map Collection입니다.
  • TreeSet과의 차이점은 키와 값이 저장된 Map.Entry를 저장한다는 점이며, 키값을 비교해서 자동으로 정렬됩니다.
// TreeMap 생성하기
TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>();

// 값을 삽입하기
treeMap.put("banana", new Integer(10));

// 가장 상위의 키값을 가져오기
scores.firstKey();

// 가장 하위의 키값을 가져오기
scores.lastKey();

# 참고자료

← 이진 탐색 트리 (BST) →