트리 종류

1. 트리의 종류

  ㅇ 순서 트리 (Ordered Tree)
     - 각 자식 노드에 순서가 부여되어 저장 위치가 고정되는 트리
       

     - 통상, 좌측부터 순서 있게 위치 함   ☞ 완전 이진 트리 참조

  ㅇ 경사 트리 (Skew Tree)
     - 모든 노드가 1개 자식 노드 만을 갖고, 경사지게 보이는 트리

  ㅇ 이진 트리 (Binary Tree)
     - 각 노드의 차수(자식 수)가 2 이하인 순서 트리

     * (이진 트리의 종류)                             ☞ 이진 트리 종류 참조
     - 전 이진 트리 (Full Binary Tree)
        . 모든 노드의 차수/자식이 0 또는 2 이어야 함

     - 포화 이진 트리 (Perfect Binary Tree)
        . 모든 노드들의 자식이 2인 (꽉찬) 트리

     - 완전 이진 트리 (Complete Binary Tree)
        . 부모,왼쪽 자식,오른쪽 자식 순으로, 꽉 채워지며 만들어지는 이진 트리

     - 힙 (Heap)
        . 부모의 값이 자식 값 보다 항상 크다 또는 작다 라는 조건을 만족하는 완전 이진 트리

  ㅇ 이진 탐색 트리 (Binary Search Tree, BST)
     - 이진 트리 구조를 갖으나, 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조
        . 좌측 자식 노드 값이 부모 노드 값 보다 작고, 우측 자식 노드 값이 부모 노드 값 보다 큼

  ㅇ 균형 트리 (Balanced Tree)
     - 이진 트리 구조를 갖으나, 하위 노드 구조가 좌우 대칭이 되도록 한 것 (例, B-tree)
        . 이진 탐색 트리를 보다 일반화시킨 트리 자료구조

  ㅇ N항 트리 (N-ary Tree, N-way Tree)
     - 일반적으로, 자식 노드의 수(차수)가 3 이상일 때를 말함
     - 한편, 자식 노드가 3 이상인 트리 구조를 총칭해서, 다중 트리(Multi-Branch Tree)라고 함