ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Tree
    공부/자료구조 2018. 7. 31. 22:04

    Tree 구조


    트리는 위와 같은 구조를 갖고 있습니다.

    용어

    • node: 트리에서 데이터를 의미
    • branch(link): 노드와 노드를 연결
    • root node: 최상위 노드
    • interior node: 자기자신 아래에 연결된 노드가 있는 형태
    • leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태
    • parent: child 노드들이 연결되어 있는 상위 노드
    • child: 부모노드 아래에 연결되어 있는 노드
    • sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드
    • degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지
    • depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수
    • level: 트리의 특정 depth를 가지는 노드의 집합
    • height: 루트노드에서부터 가장 멀리 있는 노드의 depth
    • 트리의 degree: 트리의 최대 degree
      • 위 그림에서 노드의 최대 degree는 2

    Skewed Tree (Degenerate Tree)


    Full (Perfect) Tree


    Binary Tree

    degree가 최대 2 (0 <= degree <= 2)


    Quad Tree

    degree가 최대 4 (0 <= degree <= 4)


    정의

    • root 노드를 제외한 모든 노드는 parent 노드를 1개만 가짐
    • leaf 노드를 제외한 모든 노드는 child 노드를 1개 이상을 가짐

    Tree 자료구조의 다양한 타입

    Binary Tree

    • Binary Search Tree, Heap, Digital Search Tree
    • Red-Black Tree, AA Tree, Splay Tree

    Height-Balanced Binary Tree

    • AVL Tree, T-Tree

    n-Way Tree

    • m-Way Tree
    • 2-3 Tree, 2-3-4 Tree

    Height-Balanced m-Way Tree

    • B-Tree, B+-Tree, K-d B-Tree

    Spatial Tree

    • Quad Tree, Oct Tree, R-Tree


    댓글