트리

자료구조

트리

독기품기 2024. 7. 26. 17:53

트리란?

- 원소들 간에 계층적인 관계를 나타내는 계층형 자료구조

- 원소들 간에 1:n 관계를 가지는 비선형 자료구조(순서가 존재)

- 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양 구조

- 가계도, 컴퓨터 폴더구조, 탐색과 힙의 결정트리에 사용

- N-링크/ 자식-형제 표현법

트리용어

- 노드(node) : 트리의 구성요소

- 간선(edge) : 노드를 연결하는 선 (부모 - 자식)

- 루트(root) : 부모가 없는 노드, 최상위 노드

- 서브트리(subtree) : 하나의 노드와 자손들로 이루어짐(루트를 제외한 나머지 노드들)

- 단말노드(terminal node) : 자식이 없는 노드

- 비단말노드(nonterminal node) : 자식이 있는 노드

- 조상노드(ancesor node) : 간선을 따라 루트노드까지 경로에 있는 모든 노드

- 형제노드(sibling node) : 같은 부모 노드의 자식 노드들

- 차수(degree) : 노드의 자식 노드수

- 노드의 차수 : 노드에 연결된 자식 노드의 수

- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값

- 레벨 : 트리의 각 층의 번호

- 높이 or 깊이 : 트리의 최대 레벨

- 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 즉 노드의 레벨

- 트리의 높이 : 트리에 있는 노드의 높이중에서 가장 큰 값, 즉 최대 레벨

- 숲(forest) : 서브트리의 집합, 트리에서 루트노드를 제거하면 서브트리들로만 생기는 집합

트리의 다른 표현 방법

- 중첩된 집합, 중첩된 괄호, 들여쓰기

이진트리란?

- 모든 노드가 2개의 서브트리를 가지고 있는 트리

- 트리의 모든 노드의 차수(자식의 수)를 2이하로 제한하여 전체 트리의 차수가 2이하가 되도록 정의한 트리

- 왼쪽 자식과 오른쪽 자식은 반드시 구별해야함

- 노드의 차수 최대 2 => 왼쪽 자식과 오른쪽 자식만 가짐을 의미하며 공백 노드도 자식 노드 취급

- 모든 노드의 차수가 2이하라 구현하기 편리

- 서브트리간에 순서가 존재 (왼,오)

- 일반 트리를 이진 트리로 바꾸기 위해서는 첫 자식 노드 간선만 남기고 나머지 간선을 제거 후 형제노드를 간선으로 연결한 후 시계 방향으로 45도 회전시키면 된다.

이진트리의 종류

- 포화이진트리 : 모든 레벨의 노드가 포화상태로 꽉 차 있는 트리, 높이가 h일 때 최대 노드 개수는 2^h - 1의 노드를 가진 이진트리이며 루트를 1번으로 하여 2^h -1까지 정해진 위치에 대한 노드 번호를 가진다.

- 완전이진트리 : 높이가 h일 때 레벨1부터 h-1까지는 노드가 모두 채워지며 마지막 레벨 h에서는 노드가 순서대로(중간에 빈 곳이 존재하면 x) 채워지고 높이가 h이고 노드 수가 n개일 때 (단, n < 2^h -1), 노드의 위치가 포화이진트리에서 노드 1번 ~ n번까지의 위치와 완전히 일치하는 트리이다. 하지만 n+1번부터 2^h -1번까지의 노드는 공백노드다