Tree

Tree

 트리는 정점인 Node와 정점을 연결하는 선인 간선 Edge를 이용하여 사이클이 이루어지지 않게 구성된 비선형 자료구조이다. 

트리 구조

 Tree의 개념 

• 트리는 하나의 루트 노드를 갖는다.
• 루트 노드는 0개 이상의 자식 노드를 가지고 있다.
• 자식 노드 또한 0개 이상의 자식 노드를 가지고 있다.
  
• 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. 
• 트리에는 사이클이 존재하지 않는다. -> 무방향 그래프이기 때문!

 

관련 용어

• Node: 트리에서 데이터를 저장하는 기본 요소 
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
• Sibling: 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level