트리 (Tree)
트리는 그래프 한 종류로써, 그래프에서 사이클이 존재하지 않으며, 방향성을 가진 weighted Graph이다.
해당 형태의 그래프는 계층구조를 표현하는데 특화되어 있다. 해당 특성을 통해 자료를 쉽게 조작하고 탐색할 수 있다는 특징이 있다.
출처 : https://www.geeksforgeeks.org/tree-data-structure/?ref=shm
Parent Node
루트 노드 방향으로 연결된 노드
Child Node
루트 노드 반대방향으로 연결된 노드
Root Node
트리의 가장 맨 위에 있는 노드를 root 노드라고 한다. 부모 노드가 없다.
Sibling Node
같은 부모 노드를 가진 노드
Leaf Node
자식 노드를 가지지 않은 노드들을 뜻한다.
Level
root node를 level 0으로 시작하여, 노드간의 경로를 지날 때마다 1씩 증가한다.
이진 트리 (Binary Tree)
모든 노드가 최대 두 개의 자식 노드를 가진 트리
정 이진 트리 (Full Binary Tree)
모든 트리의 자식 노드가 0 또는 1개인 트리
포화 이진 트리 (Perfect Binary Tree)
모든 리프 노드의 레벨이 같고 리프노드가 아닌 노드는 모두 2개의 자식을 갖는 트리
완전 이진 트리 (Complete Binary Tree)
모든 리프 노드의 레벨이 최대 1차이가 나고 왼쪽에서부터 차례대로 채워나가는 트리이다. 완전 이진 트리의 부분집합이 포화 이진 트리이다.
