트리 구조

트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.

모델에 대해서는 트리 구조 (모델) 문서를 참고하십시오.

이진 트리

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

유명한 트리 자료 구조

• 자가 균형 이진 탐색 트리
• AVL 트리
• 레드-블랙 트리
• 스플레이 트리

기타

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

같이 보기

• 힙
• 연결 리스트
• 그래프 이론
• 분류:트리 구조