Forever Learning!
If there is any mis-information please send message.

1 분 소요

자료 구조 목차

  • Data-Structure
    • Linear
      • Static
        • Array
      • Dynamic
        • Linked List
        • Stack
        • Queue
    • Non Linear
      • Tree
      • Graph

이진 트리의 종류

이전에는 트리가 무엇인지 대해서 알아보았다. 이번에는 어떤 종류의 트리가 있는지 알아보겠다.

정 이진 트리(Full Binary Tree)

정이진트리는 모든 노드가 자식을 0 또는 2개를 갖고 있는 것을 뜻한다. 아래와 같은 구조로 나타내진다.

        18
      /    \
    15      30
   /  \    /  \
  40  50  100 40

---------------------

        18
       /  \
      15  20
     /  \
    40  50
   /  \
  30  50
  
---------------------

        18
       /  \
      40  30
         /  \
        100 40

완전 이진 트리(Complete Binary Tree)

완전이진트리는 마지막 레벨을 제외한 모든 레벨이 가득 찬 트리를 뜻합니다. 또한 마지막 레벨도 가능하면 왼쪽은 모든 키가 있어야합니다.

        18
      /    \
    15      30
   /  \    /  \
  40  50  100 40

---------------------

        18
      /    \
    15      30
   /  \    /  \
  40  50  100 40
 / \  /
8  7  9

완전 이진 트리는 이진 힙(Binary Heap)에서 사용된다. 살짝 어디서 본거같은 느낌이다. 어디서 봤냐면 Priority Queue에 대해서 적다가 어떻게 정렬되는지 찾다가 나온 단어이다.
아직도 자세히 알지는 못한다. 알아서 공부하자;;;;;;;;

완벽 이진 트리(Perfect Binary Tree)

완벽이진트리는 모든 내부 노드가 꼭 2명의 자식을 필수적으로 갖고 있어야한다.

        18
      /    \
    15      30
   /  \    /  \
  40  50  100 40

---------------------

        18
      /    \
     15    30

완전이진트리와 다른 점은 완전이진트리는 마지막 레벨에 무조건 모든 자식들이 있지않아도 되지만 완벽이진트리는 마지막 레벨에도 모든 자식들이 있어야한다.

균형 이진 트리(Balanced Binary Tree)

균형이진트리라는 것은 왼쪽 노드와 오른쪽 노드의 depts가 2이상(1초과) 차이 나지않는 것을 말한다.
주로 알고리즘으로 나오는 문제로는 균형이진트리인지 아닌지 확인한 수 균형이진트리로 만드는 것을 파악해두는 것이 좋다.
균형 이진 트리에 대해서는 너무 깊게 설명하면 나도 머리가 아플 것 같아 알고리즘 관련 포스팅을 할 때 적도록 하겠다.

이것으로 이진 트리의 종류에 대해서 알아보았다.
다음으로는 자바에서 사용되는 TreeSet에 대해서 적어보겠다.

균형이진트리에 대해서 자세히 적지는 않았지만 구글을 통해서 금방 찾을 수 있으니 한번 확인해보자

References

참고