트리 구조

위키백과 ― 우리 모두의 백과사전.

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

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

[편집] 유명한 트리 자료 구조

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

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


Other trees:

  • B-트리 (2-3 트리, B+ 트리, B*-트리)
  • DSW 알고리즘
  • 춤추는 트리
  • R-트리
  • 기수 트리
  • 스킵 리스트