진리 블로그

트리(Tree)
  - Linked List로 표현할 때 가장 효과적이다
  - 계층형 구조(부모 자식구조, 족보구조)
 
트리 구조의 용어
  - 근노드(root node) : 최상위 노드
  - 노드(node) : 트리의 기본요소로 하나의 값
  - 단노드(Terminal node, leaf nod) : 자식이 없는 노드
  - 레벨(Level) : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식노드는 L+1
  - 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대의 레벨
  - 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수
  - 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

트리의 운행법
 
     찾아가는방식       표현방식                       운행법
        Preorder            prefix            Root(연산자) → Left → Right
         Inorder              Infix             Left → Root(연산자) → Right
       Postorder           Postfix           Left → Right → Root(연산자)



이진트리(Binary Tree)
  : Degree가 2이하인 노드들로 구성된. 다시말해 자식이 둘 이하인 노드들로만 구성된 트리를 말한다.

이진트리의 주요 특성
  - 깊이가 n인 이진트리의 최대 노드수 = 2ⁿ-1

이진트리의 종류
  - 정이진 트리(Full Binary Tree)
      : 깊이가 n일 때 전체 노드 수가 2ⁿ-1개의 노드이다.
  - 전이진 트리(Complete Binary Tree)
      : 노드의 수가 n개일때, 정이진 트리의 각 노드에 붙인 1~n의 일련번호와 1:1대응되는 트리
        중간에 빈 부분이 있으면 전이진 트리가 될 수 없다
  - 사향이진 트리(Skewed Binary Tree)
      : 왼쪽 또는 오른쪽으로만 기울어진 트리, 즉 왼쪽 또는 오른쪽 자식이 없는 노드들로만 구성된 트리
        사향이진 트리는 공간 낭비가 심하다.


B-트리
  : 한노드 안에 있는 키 값은 오름차순을 유지시켜 많은 데이터를 빠르게 검색할 수 있게 한 트리

신장트리
  : 그래프에서 간선들이 사이클이 되지 않도록 만든 트리