트리 종류

(2019-11-12)

Ordered Tree, 순서 트리

1. 트리의 종류

  ㅇ 순서 트리 (Ordered Tree)
     - 각 자식 노드에 순서가 부여되어 저장 위치가 고정되는 트리
       
     - 통상, 좌측부터 순서 있게 위치 함  ☞ 완전 이진 트리 참조

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

     - 전 이진 트리 (Full Binary Tree)
        . 각 레벨에 노드들이 꽉 차있는 이진 트리

     - 포화 이진 트리 (Perfect Binary Tree)
        . 모든 단말 노드의 레벨이 동일하며, 최하위 자식 노드들이 모두 차 있음

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

     -  (Heap)
        . 부모의 값이 자식 값 보다 항상 크다 또는 작다 라는 조건을 만족하는 완전 이진 트리이진 탐색 트리 (Binary Search Tree, BST)
     - 이진 트리 구조를 갖으나, 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조
        . 좌측 자식 노드 값이 부모 노드 값 보다 작고, 우측 자식 노드 값이 부모 노드 값 보다 큼

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

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


[트리] 1. 트리 2. 트리 용어 3. 트리 종류 4. 이진 트리 5. 이진 탐색 트리 6. 스패닝 트리 7. 트리 순회 8. B 트리 9. 10. 멀티캐스트 트리

 
        최근수정     요약목록     참고문헌