Tree

트리

계층을 가지도록 데이터를 나열한 것

트리의 특징

• 노드는 데이터와 자식 노드들로 이루어져 있다
  
  
• 값의 중복이 없다

트리의 구조

트리의 용어

• 루트 노드

  트리의 가장 윗부분에 있는 노드

• 리프 노드

  가장 밑 부분에 있는 노드

• 부모 노드

  특정 노드의 상위 노드

• 자식 노드

  특정 노드의 하위 노드

• 형제 노드

  부모가 같은 노드

• 조상 노드

  부모의 부모 노드들

• 자손 노드

  자식의 자식노드들

• 레벨

  루트로부터의 거리
  루트를 0 or 1중 무엇으로 보느냐에 따라 달라짐

• 차수

  자식 노드의 수 | 2이면 이진트리

• 트리의 높이

  루트에서 가장 먼 리프 노드까지의 거리

트리의 종류

• 이진트리: 최대 차수가 2인 트리

  이진탐색트리, 힙트리, AVL, 레드블랙

• 삼진트리: 최대 차수가 3인 트리

  B+트리(차수에 따라 가변적)

• N진트리: 최대 차수가 N인 트리