트리

자료구조에는 데이터를 저장하는 방식에 따라 선형형식, 비선형형식으로 나뉜다.

• 선형 구조 : 데이터를 1:1 관계로 하나씩 나열시킨 구조로, list, stack, queue가 해당 구조에 해당한다.
• 비선형 구조 :  데이터를 1:n 관계로 나열 시킨 구조로 Tree가 해당 구조에 해당한다.

 그리고 비선형 구조 중에서 가장 기초적인 자료구조는 Tree이다. Tree란 1개의 노드에 다수의 노드를 연결하는 자료구조로, 데이터 사이의 계층 관계로 만들어진 계층형  자료 구조이다.

 

트리 관련 용어

 트리는 하나의 노드에 여러개의 노드를 연결해서 형성하는 1:n 관계인 자료구조로, 트리에서 사용하는 용어가 따로 존재한다.

용어	설명
간선	노드와 노드를 연결하는 연결 선
레벨	루트로 부터 떨어져 있는지에 대한 값으로, 루트의 레벨은 0이며, 하나씩 아래로 뻗어나갈수록 1씩 증가
차수	노드가 갖는 자식의 수로, 노드의 간선 갯수
높이	루트로 부터 가장 멀리 떨어진 리프까지의 거리로, 레벨의 최댓값을 의미

용어	설명
루트 노드	트리의 가장 윗부분에 위치하는 노드로, 트리의 시작 노드를 의미
말단 노드	트리의 가장 아랫부분에 위치하는 노드로, 연결된 노드가 없는 노드를 의미
부모 노드	간선으로 연결된 위쪽 노드로, 부모 자식 관계에서 위쪽에 위치한 노드
자식 노드	간선으로 연결된 아래쪽 노드, 부모 자식 관계에서 아래쪽에 위치한 노드
형제 노드	같은 부모 노드를 가지는 노드

용어	설명
서브 트리	트리 안의 노드를 루트로 정하고, 루트노드의 간선으로 연결되어 있는 트리

 

이진 트리

 트리는 하나의 부모노드에 여러 자식노드를 가지고 있는 다차수의 형식을 가지고 있다. 하지만 트리의 구조를 일정하게 제한하여 연산을 단순하고 명확하게 하기 위해서 트리의 모든 차수를 2 이하로 제한한다. 이를 이진트리라고 하는데, 이진트리란 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리로, 차수가 2 이하인 트리를 의미한다.

이진트리의 시작은 항상 왼쪽부터 시작한다. 즉, 이진 트리는 왼쪽 노드를 기준으로 한다. 그리고 이진트리에도 형태에 따라 완전 이진트리,편향 이진트리로 나뉜다. 

 편향 이진트리란 왼쪽이나 오른쪽 서브트리만 가지고 있는 이진트리로, 한쪽 반향으로만 가지고 있다. 반대로 완전 이진트리란 마지막 레벨을 제외한 모든레벨의 노드가 채워져 있는 이진트리로, 마지막 레벨은 왼쪽 부터 오른쪽 방향으로  노드를 채운다. 이때 완전 이진트리에서 마지막 레벨을 모두 채운 이진트리가 있는데, 이를 포화 이진트리라고 한다.

편향 이진트리	완전 이진트리	포화 이진트리

 

 모든 트리는 이진 트리로 구성되어 있지 않다. 그래서 트리를 기준에 따라 이진트리로 변경할 수 있어야 한다.

트리를 이진 트리로 변경하는 방법

1. 서브트리의 모든 노드의 왼쪽 간선을 제외한 모든 노드를 삭제 2. 형제 노드끼리 연결

그리고 트리를 변형시킨 이진트리를 다시 정렬하면 다음과 같다.