[자료구조] 트리(Tree)

https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

트리(Tree)

    - 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조

    - 단방향 그래프의 한 구조로, 나무를 거꾸로 뒤집어 놓은 것처럼 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 가짐

    - 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조

 

트리의 구조

    - 루트(Root) : 트리 구조가 시작되는 꼭짓점 데이터

    - 노드(Node) : 트리 구조에서 연결된 각각의 데이터로, 두 개의 노드가 상하 계층으로 연결되면 각각 부모 노드(Parent Node)와 자식 노드(Child Node)로 나뉘고, 자식이 없는 노드는 리프 노드(Leaf Node)라고 부름

    - 서브 트리(Sub Tree) : 루트에서 뻗어나오는 큰 트리 내부에서 트리 구조를 갖춘 작은 트리

 

트리 구조의 측정

    - 깊이(Depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이

    - 레벨(Level) : 같은 깊이를 가지고 있는 노드로, 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 부름

    - 높이(Height) : 리프 노드를 기준으로 루트까지의 높이