트리 구조

이진 트리

트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드^[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드^[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

유명한 트리 자료 구조

스스로 균형을 맞추는 이진 탐색 트리

• AVL 트리
• 레드-블랙 트리
• 스플레이 트리
• 속죄양 트리

기타

• 신장 트리, 최소 비용 신장 트리
• B-트리, 2-3 트리, B+ 트리, B*-트리
• DSW 알고리즘
• 춤추는 트리
• R-트리
• 기수 트리
• 스킵 리스트