이진 트리의 종류와 개념

앞서, 트리구조란?

이전 포스팅에서 본대로 트리구조는

아래와 같이 자바스크립트로 심플하게 구현할 수 있다.

그러나 아래 구조에서는 한 Node에 3개 이상의 자식노드도 제한없이 추가할 수 있다.

class Tree {
  constructor(value) {
    this.root = new Node(value);
  }
}

class Node {
  children = [];
  constructor(value) {
    this.value = value;
  }

  push(value) {
    this.children.push(new Node(value));
  }
}

 

그러므로 이진탐색에 쓰이기 위한 트리구조는 좀 더 제약이 필요한데, 실제 구현은 다음 포스팅 때 하겠다.

그전에 일단 이진트리가 무엇인지에 대해 정확히 알아보도록 하자.

 

 

이진트리란?

그러나 이진탐색에 필요한 이진트리는 

모든 노드들이 둘 이하(0,1,2 개)의 자식을 가진 트리라는 제한이 필요하다.

 

 

정이진트리일 때 아래와 같은 노드의 개수가 발생한다.

 

이진트리의 종류

 

이진트리에는 총 5가지 종류가 있다.

아래 이미지 순서대로 진이진트리(Full), 완전이진트리(Complete), 편향된 이진트리(Degenerate), 포화이진트리(Perfect), 균형이진트리(Balanced)

 

 

 

진이진트리(Full)란?

자식이 1개인 경우가 없어야 한다. 0개이거나 2개여야 한다.

위 왼쪽 이미지에서도 3번노드의 자식이 하나밖에 없기 때문에 진이진트리라 볼 수 없다.

반면에 오른쪽 이미지의 3번 노드는 아무런 자식이 없지만 진이진트리라고 볼 수 있다.

 

 

완전 이진트리(Complete)란?

완전 이진트리는 아래와 같은 조건을 만족해야한다.

1. 마지막 레벨을 제외하고는 모든 노드가 차있어야한다.

2. 마지막 레벨은 비어있는 노드가 있을 순 있지만 왼쪽에서 오른쪽으로 채워져야한다.

 

이 완전 이진트리에 계속 노드가 쌓이다 마지막 레벨에도 모든 노드가 꽉 차게 되면

다음에 설명할 포화이진트리가 된다.

 

 

편향이진트리(Degenerate)란?

이진트리 중에서 가장 시간복잡도가 안 좋은 트리이다. 선형 구조로 되어있으며, O(N)의 시간복잡도를 가진다.

사실 이 구조는 연결리스트와 동일하다고도 볼 수 있다.

 

 

포화이진트리(Perfect)란?

이진트리 중에서도 모든 노드가 자식 2개씩 가지고 있고, leaf노드가 모두 같은 레벨일때는 포화이진트리라고 한다.

이 글 최상단의 이미지처럼 높이가 h인 포화 이진트리는 2의 k+1 제곱 - 1의 특징을 갖는다.

 

균형이진트리(Balanced)란?

균형이진트리는 leaf노드의 level차이가 1 이하인 트리를 말한다.

그러므로 모든 완전이진트리(Complete)와 포화이진트리(Perfect)와 균형이진트리일 수 밖에 없다. 

 

 

이렇듯 트리의 구조, 상태를 나타내는 여러 명칭에 대해 정리해보았다.

다음으로는 이 트리 구조를 이용하여 어떤 알고리즘을 구현하여 어떤 문제를 해결할 수 있는지에 대해 써보겠다.

• 수식트리(Expression Tree)
• 허프만 코딩 트리(Huffman coding tree)
• 이진 검색 트리(Binary Search Tree, BST)
• 우선 순위 큐(PQ)

 

 

 

참고자료:

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

https://yoongrammer.tistory.com/69