Tree

Tree

• 계층적 구조를 나타내는 자료구조

• 부모-자식 관계의 노드들로 구성, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태

• 자식 -> 부모, 등으로 순환 할 수 없음, 무조건 부모 -> 자식 방향으로만 뻗어나감

• Linked List의 장점 을 가지고 있음( 데이터 삽입, 삭제시 데이터들을 이동하지 않아도 되는것)

• Linked List의 단점을 보완함(검색시 노드의 처음부터 찾아가야 하는 것, 이진 탐색)

• 노드가 3개 붙으면 ternary tree, 2개 붙으면 binary tree 라고 함, 주로 binary tree를 가장 많이 씀

 

Tree 용어 정리

 

• 부모(parent) 노드 : 어떤 노드 바로 위에 연결되어있는 노드

• 자식(child) 노드 : 어떤 노드 바로 아래에 연결되어 있는 노드

• 형제(sibling) 노드 : 같은 부모를 가지는 노드

• 조상(ancestor) : 어떤 노드에서 root 노드에 이르는 경로상에 있는 노드들

• 자손(descendent) : 어떤 노드의 자식 노드를 포함하여, 아래쪽에 있는 노드들

 

 

• 루트(root) : 부모가 없는 노드

• 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리

 

 

 

 

• 잎(leaf) 노드 : 자식 노드가 하나도 없는 노드, 외부(external) 노드라고도 불림

• 내부(internal) 노드 : 잎노드가 아닌 노드, 자식 노드를 하나라도 가지고 있는 노드

 

 

 

 

 

 

 

• 수준(level) : 트리의 각 계층에 매겨지는 번호, root 노드의 level 은 1, 한층씩 내려갈 수록 1씩 증가

• 높이(height) : 트리에 속한 노드의 최대 수준, 위 트리의 높이는 4