Tree 트리 ?

그래프의 여러 구조중에서 일방향? 단방향? 그래프의 한 구조다.

그 모습이 너무 나무와 닮아 있어서 트리 구조라는 이름이 붙어졌다.

하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 띄우고 있다.

마치 가계도와 흡사해 보이는 이 트리구조를 간략하게 정의하면

데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조

데이터를 순차적으로 나열시킨형태인 선형구조가 아니라!!

하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조이다.

계층적으로 표현이 되며, 아래로만 뻗기 때문에 사이클(cycle)이 없다.

트리구조에는 루트(Root) 라는 하나의 꼭지점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.

이 데이터들을 노드(Node) 라고 하며, 상위 노드와 하위노드가 연결되면 부모/자식 관계를 가지게 된다.

자식이 없는 노드는 나무 의 잎과 같다고 하여 리프 노드(leaf Node) 라고 한다.

이 자료구조는 높이와 깊이를 잴 수 있다.

루트에게서 자신에게 걸리는 거리를 레벨이라고 부른다 루트는 레벨 1이다.

루트부터 가장 안쪽에있는 노드까지의 레벨을 트리의높이(Height) 라고 한다.

반대로 특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이(depth) 라고 한다.

같은 레벨에 나란히 있는 노드들은 형제 노드(sibling Node) 로 표현하고 있습니다.

루트에서 뻣어나오는 큰 트리의 내부에 트리모양새를 갖춘 작은 트리를 서브트리라고 부른다.

트리의 실사용?

쉽게 생각하면 컴퓨터의 디렉토리구조 (파일시스템)

월드컵 토너먼트 대진표 , 가계도(족보), 조직도 등등..