Tree란 무엇인가?

  • 계층적 구조를 가지고 있습니다.
  • 자식 노드를 가지고 있지 않은 가장 마지막 Node를 Leaf Node라고 합니다.
  • 노드와 노드는 간선(Edge)으로 이루어져있습니다.

Tree는 어디에 사용될까?

와 같은 곳에서 Tree 구조를 사용합니다.

Tree에는 많은 종류의 Tree가 있다.

Tree 종류를 보면 트리에도 여러 종류의 트리가 있는 걸 볼 수 있습니다. 이것들은 다 트리의 규칙에 맞게 정의된, 같은 규정을 따릅니다. 서로 약간씩 다르게 특별한 프로퍼티를 추가하거나 약간의 규칙이 더해지거나 하는 식이죠.

이번에 중점적으로 공부할 트리의 종류는

  • Trees
  • Binary Trees (이진 트리)
  • Binary Search Trees (이진 탐색 트리)

세 가지입니다.

Trees

일반적인 트리의 모형은 다음과 같습니다.
자식이 0개인 노드도 있고, 자식이 2개, 3개인 노드도 있습니다. 즉, 부모 노드가 몇 개의 자식노드를 가져야한다라는 규칙이 없습니다.


Binary Trees (이진 트리)

하지만 이진트리는 각 노드가 최대 두 개의 자식을 가저야 한다는 조건이 있습니다.
자식이 0개이거나 1개거나 2개일 수 있습니다. 그렇지만 3개는 안되는거죠.

위에 트리는 트리일까요?, 이진트리일까요?
트리는 맞지만, 이진트리는 아닙니다. 처음 root 노드에서부터 보면 자식 노드가 3개이기 때문에 이진트리라고 할 수 없습니다.

Binary Search Trees (이진 탐색 트리)

이진 탐색 트리는 이진 트리입니다.

둘의 차이점이라면 이진 트리의 특별한 버전이라고 생각하면 될 것 같습니다. 이진 탐색 트리는 특별한 방식으로 정렬이 되어있습니다.

  • 부모 노드의 왼쪽에 있는 모든 노드는 언제나 부모보다 작고,
  • 부모 노드보다 오른쪽에 있는 모든 노드는 언제나 부모보다 큽니다.

📝 Binary Search Tree를 사용하는 이유

이진 탐색 트리를 사용하면 찾아야하는 값을 빠르게 찾을 수 있습니다. 정렬되어 있는 데이터이기 때문에 찾아야 하는 값보다 작으면 왼쪽을, 크면 오른쪽을 탐색하면 되기 때문에 데이터 검색의 횟수가 반으로 줄어듭니다.