트리(Tree) 자료구조

트리(Tree) 자료구조

노드와 노드가 에지로 연결된 그래프의 특수한 형태

 

 

트리의 구성 요소

트리의 구성 요소

 

• 노드 : 데이터의 index와 value를 표현하는 정보의 단위
• 에지 : 노드와 노드의 연결 관계를 나타내는 선
• 루트 노드 : 트리의 최상단 노드
• 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
• 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드
• 리프 노드 : 트리의 최하단 노드 (자식 노드가 없는 노드)
• 서브 트리 : 전체 트리에 속한 작은 트리

 

 

트리의 특징

• 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
• 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다.
• 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.