Tree

Tree 자료구조는 데이터를 마치 나무(흡사 세피로스의 나무) 형태로 저장하는 자료 구조 입니다.

세피로프의 나무

-Tree는 일반적으로 대상정보의 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용하는 비선형 자료구조입니다.

• 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 됩니다.
• Tree는 그래프의 한 종류이며 사이클이 없습니다.
• 대용량의 데이터를 저장할때도 많이 쓰입니다.

용어

• Node: 트리구조의 교점입니다.
  Node가 데이터를 가지고 있고 또한 자식노드를 가지고 있습니다.
  Tree 자료구조는 노드를 기본으로 구성됩니다.
• Root Node: Tree 구조의 가장 위 노드, 즉 시작점이 되는 node입니다.
• Edge: Tree를 구성하기 위해 노드와 노드를 연결하는 line 입니다.
• Level: Tree의 특정 깊이를 가지는 노드의 집합입니다.
• Degree: 하위 tree 개수 / 각 노드가 지닌 가지의 수를 말합니다.
• Internal Node: leaf노드를 제외한 중간에 위치한 노드들을 말합니다.
• Leaf Node: 하위에 다른 노드가 연결되어 있지 않은 노드입니다.

  🚨 Tree의 속성 중 가장 중요한 것이 Root 노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다는 것 입니다.

Binary(이진) Tree

두개의 자식 노드를 가진 트리를 Binary Tree라고 합니다.

• 하나의 노드에 LEFT or RIGHT만 존재한다고 표현합니다.
• LEFT node는 부모 node의 값 보다 크면 저장되고, RIGHT node는 작으면 저장합니다.
  
• 이진 트리는 검색을 효율적으로 할 수있습니다. 원하는 값을 찾을 때까지, 현재 node의 값이 원하는 값보다 크면 왼쪽으로, 작으면 오른쪽으로 움직입니다.