자료구조 트리 Tree

나무의 형태를 가지고 있다

 

하나의 뿌리로부터 가지가 사방으로 뻗은 형태이다

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

데이터를 순차적으로 나열시킨 선형 구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

 

Tree의 구조

• 깊이 (depth) 루트로부터 하위 계층의 특정 노드까지의 깊이 -> A의 깊이는 0이고, B와C는 1, D,E,F,G는 2
• 레벨 (level) 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라 한다 -> A는 level 1, B,C는 level 2
• 높이 (height) 리프 노드를 기준으로 루트까지의 높이 (리프 노드의 높이를 0으로 본다) -> H,I,E,F,J의 높이는 0
• 서브 트리 (Sub tree) 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리 -> (D,H,I), (C,F,G,J) 등