🔧변경내용🔨
제목 날짜 내용 발행일 23.03.15
📌들어가기에 앞서
해당 포스터는 자료구조 학습 내용 중
Tree기초이론에 대한 내용을 정리한 것입니다.
📖 Tree의 정의
-
자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다.
-
정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습
-
그래프의 여러 구조 중 단방향 그래프의 한 구조로,
-
하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아다고 해서 트리 구조라고 부른다.
-
트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조
-
데이터를 순차적으로 나열시킨 선형 구조가 아니다
-
하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
-
트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(
cycle)이 없다. -
여기서 사이클이란
- 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 표현한다.
따라서 트리는 사이클(cycle)이 없는 하나의 연결 그래프 (Connected Graph)라고 할 수 있다.
📖 Tree의 구조와 특징
-
트리 구조는 루트(
Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. -
각 데이터를 노드(
Node)라고 한다. -
두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계이다.
-
위 그림에서
A는B와C의 부모 노드(Parent Node)이고, -
B와C는A의 자식 노드(Child Node).
-
-
자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(
Leaf Node)라고 부른다.
- 자료구조
Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.
깊이 (depth)
-
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다.
-
루트 노드는 지면에 있는 것처럼 깊이가
0-
위 그림에서 루트
A의 깊이는0이고, -
B와C의 깊이는1이다. -
D,E,F,G의 깊이는2이다.
-
레벨(Level)
-
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현 할 수 있다.
-
깊이가
0인 루트A의level은1 -
깊이가
1인B와C의level은2 -
D,E,F,G의 레벨은3
-
-
같은 레벨에 나란히 있는 노드를 형제 노드(
Sibling Node) 라고 한다.
높이(Height)
-
트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.
-
리프 노드와 직간접적으로 연결된 노드의 높이를 표현한다.
-
부모 노드는 자식 노드의 가장 높은 높이 값에
+1한 값을 높이로 가진다. -
트리 구조의 높이를 표현할 때는 각 리프 노드의 높이를
0으로 놓는다. -
위 그림에서
H, I, E, F, J의 높이는0 -
D와 G의 높이는 1입니다. B와 C의 높이는 2입니다. 이때 B는 D의 height + 1을, C는 G의 height + 1을 높이로 가집니다. 따라서, 루트 A의 높이는 3입니다.
서브 트리(Sub tree)
-
트리 구조의 루트에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부른다.
-
(D, H, I)로 이루어진 작은 트리도 서브 트리이고,(B, D, E)나(C, F, G, J)도 서브 트리입니다.
자료구조는 자료의 집합을 구조화하고, 이를 표현하는 데에 초점이 맞춰져 있다.
용어정리
-
노드(Node) : 트리 구조를 이루는 모든 개별 데이터
-
루트(Root) : 트리 구조의 시작점이 되는 노드
-
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
-
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
-
리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
📖 Tree의 실사용 예제
-
가장 대표적인 예제는 컴퓨터의 디렉토리 구조
-
어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.
-
모든 폴더는 하나의 폴더(루트 폴더,
/)에서 시작되어, 가지를 뻗어나가는 모양새를 띈다.
-
하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있다.
-
위 그림처럼, 제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일하다.
-
사용자들이 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있습니다.
트리의 다른 예시
- 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등
📚 레퍼런스
코드스테이츠 수업자료
