• 트리는 1개 이상의 유한한 개수의 노드집합입니다.
• 루트노드와 0개 이상의 겹치지않는 하위 노드로 이루어져있죠.

용어

1. path : edge에 의해 연결된 노드들의 집합입니다.

2. root Node : 최상위의 노드를 뜻합니다.

3. 부모, 자식, 형제 : 현재노드의 직계상위를 부모노드라하며, 아래층의 노드를 자식노드, 같은 부모를 둔 노드를 형제노드라 합니다. 부모노드의 부모는 조부모, 직계상위노드는 조상 뭐 이런말도 있습니다.

4. leaf : 자식이 없는 말단 노드를 뜻합니다.

5. subtree큰 tree에 속한 작은 tree를 뜻합니다.

6. 노드의 degee : 하위 서브트리의 개수를 뜻합니다.

   

Complete Binary Tree (완전 이진 트리)

• 가장 마지막 레벨을 제외한 모든 노드들이 꽉 차 있고, 마지막 레벨은 왼쪽부터 차례대로 채워져 있는 트리입니다.

Full Binary Tree(포화 이진 트리)

• 마지막 레벨까지 모두 충족된 이진트리를 뜻합니다.
• 레벨별 노드는 공비가 2인 등비수열이라 볼 수 있으므로 높이가 h인 이진트리가 가질 수 있는 최대 노드수는 2^h -1입니다.

BinarySearchTree(이진탐색트리)

이진탐색트리는 기존 트리에비해 효율적인 탐색능력을 유지하며, 빈번한 자료입력 및 삭제를 가능하게끔 고안되었습니다. 특징은 다음과 같습니다.