트리스타나

트리는 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조이다. 그러나 실제 계층 관계가 없는 자료들을 트리로 표현해서 같은 연산을 더 빠르게 하는 용도로도 많이 사용한다.

트리의 구성 요소

• 노드 (node)
• 간선 (edge)

노드 간에는 상/하위 관계가 있으며, 두 노드가 연결되었을 때 한 노드는 좀더 상위, 다른 노드는 좀더 하위에 있어야 한다.

• 부모 (parent) : 두 연결된 노드 중 상위 노드

• 자식 (child) : 두 연결된 노드 중 하위 노드

• 형제 (sibling) : 부모 노드가 같은 두 노드

• 선조 (ancestor) : 부모 노드와 그의 부모들을 통틀어서

• 자손 (descendant) : 자식 노드와 그의 자식들을 통틀어서

• 루트 (root) : 다른 모든 노드들을 자손으로 갖는 노드

• 리프 (leaf) : 자식이 하나도 없는 노드

• 깊이 (depth) : 루트에서 어떤 노트에 도달하기 위해 거쳐야 하는 간선의 수