트리 (Tree) 구조
트리 구조(나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.
주로 이진 트리 (Binary Tree) 형태 구조로 많이 사용되고, 탐색 알고리즘 구현에 많이 사용된다.
트리 용어
- Node : 트리에서 데이터를 가지고 있는 기본 요소
- Root Node (뿌리 노드) : 트리에서 가장 위에 있는 노드
- Parent Node (부모 노드) : 한 노드에 연결된 이전 노드
- Child Node (자식 노드) : 한 노드에 연결된 하위 Level의 노드
- Leaf Node (Terminal Node) : Child Node가 없는 노드
- Sibling (형제) : 같은 Parent Node를 가진 노드
- Level : 노드의 깊이를 나타낸다. 가장 위에 위치한 노드를 Level 0으로 하고 하위 Branch로 내려갈수록 Level이 올라간다.
- Depth (깊이) : 한 트리에서 가질 수 있는 Level
그래프와 트리
트리는 그래프의 일종이라고 앞에서 언급했다. 그러면 차이점은 뭘까?
위 그림에서 알 수 있듯이, 그래프는 순환을 한다는 차이점이 있다.