알고리즘/Tree

트리

코딩 화이팅 2023. 2. 28. 11:40
  • 비선형 구조
  • 원소들 간에 1(부모):N(자식) 관계를 가지는 자료구조
  • 원소들 간에 계층관계를 가지는 계층형 자료구조
  • 한 개 이상의 노드로 이루어진 유한 집합
    • 노드 중 최상위 노드를 루트(root)(부모X 자식만 있고 부모는 없다.)라고 한다.
    • 나머지 노드들은 n(>=0)개의 분리 집합 T1,...,TN으로 분리될 수 있다.(간선을 끊을 수 있다.)
  • 이들 T1,...TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다.

트리 용어

  • leaf노드(external node) : 부모만 있고 자식이 없는 노드
  • internal node : 자식의 수가 1개 이상있는 노드
  • 노드: 트리의 원소
    트리 T의 노드-A,B,C,D,E,F,G,H,I,J,K
  • 간선 : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결(위계, 방향성)
  • 루트 노드(root node) : 트리의 시작 노드
    트리 T의 루트 노드 - A
  • 경로(Path) : 간선들로 연결된 노드를 순서대로 나열한 것
  • 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들
    B,C,D는 형제 노드
  • 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
    K의 조상 노드 : F,B,A
  • 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
  • 자손 노드 : 서브 트리에 있는 하위 레벨(루트 노드와의 거리)의 노드들
    B의 자손 노드 : E,F,K
  • 차수
    • 노드의 차수 : 노드에 연결된 자식 노드의 수
      B의 차수 : 2, C의 차수 : 1
    • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
      트리 T의 차수 : 3
    • 단말 노드: 차수가 0인 노드, 즉 자식 노드가 없는 노드
  • 높이(height)
    • 깊이(depth), 레벨(level)과 비슷
    • 노드의 깊이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
    • 노드의 높이 : 말단 노드에서 해당 노드까지의 가장 긴 거리
      B의 높이=1, F의 높이=2
    • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨
      트리 T의 높이=3

트리의 조건

  • 부모:자식=1:N
  • 하나의 자식은 둘 이상의 부모X
  • 노드의 개수가 N개->간선(->)의 개수 N-1개
  • 원소가 하나이거나 비어있어도 트리.
  • 사이클이 있으면 안된다.

이진 트리

  • 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리
  • 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
    • 왼쪽 자식 노드
    • 오른쪽 자식 노드
  • 레벨 i에서의 노드의 최대 개수는 2^i개
  • 높이가 h인 이진 트리가 가질 수 있는 노드의 최대 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다.

Full 이진 트리

  • 모든 노드의 자식이 2개 또는 0개인 트리
  • leaf node가 아닌 node는 자식을 꼭 두 개 가져야만 한다.

Perfect 이진 트리

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

완전 이진 트리

  • 높이가 h이고 노드 수가 n개일 때(단, h+1<=n<2(h+1)-1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
  • 마지막 레벨 빼고 모든 레벨이 다 차있어야됨.
  • 마지막 레벨은 왼쪽부터 채워야됨.

편향 이진 트리

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리

배열을 이용한 이진 트리의 표현

  • 이진 트리에 각 노드 번호를 다음과 같이 부여
  • 루트의 번호를 1로함
  • 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n(레벨의 시작번호)부터 2^(n+1)-1(레벨의 끝 번호)까지 번호를 차례로 부여
  • 노드 번호가 i인 노드의 부모 노드 번호를 알려면 => i/2
  • 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 => 2*i
  • 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 => 2*i+1
  • 레벨 n의 노드 번호 시작 번호 => 2^n
  • 노드 번호를 배열의 인덱스로 사용(1번부터)
  • 높이가 h인 이진 트리를 위한 배열의 크기=>2^(h+1)
package test2;

public class test1 {
	public static void main(String[] args) {
		char[] arr = { '\u0000', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
		
		int parent=1;
		int left=parent*2;
		int right=2*parent+1;
		
		System.out.printf("idx: %d, node: %c\n", left, arr[left]);
		System.out.printf("idx: %d, node: %c\n", right, arr[right]);
		
		int leftChild=8;
		int parent2=leftChild/2;
	}
}
//
idx: 2, node: B
idx: 3, node: C

이진트리 순회

순회란 트리의 각 노드를 중복되지 않게 전부 방문하는 것. 트리는 비선형구조이기 때문에 선형구조에서와 같이 선 후 연결 관계를 알 수 없다.

전위 순회-부모 노드 방문 후, 자식 노드를 좌,우 순서로 방문(VLR)

  1. 현재 노드n을 방문하여 처리한다.->V
  2. 현재 노드 n의 왼쪽 서브 트리로 이동한다.->L
  3. 현재 노드 n의 오른쪽 서브 트리로 이동한다.->R
//전위순회
package test3;

public class test1 {
	static char[] arr;
	static int n;
	
	public static void main(String[] args) {
		arr=new char[] {'\u0000','A','B','C','D','E','F','G','\u0000','\u0000','H','I'};
		n=arr.length;
		traverse(1);//1번 노드부터 순회 시작, 1번 노드부터 스택에 올리기.
	}

	private static void traverse(int i) {//i번째 노드의 순회
		if (i<=n-1) {
			//V: 자기 자신을 방문 처리
			if (arr[i]!='\u0000') {
				System.out.print(arr[i]+" ");
				//L : 왼쪽 트리로 탐색 이어나감
				traverse(i*2);
				//R : 오른쪽 트리로 탐색 이어나감
				traverse(i*2+1);
			}
		}
	}
	
}
//
A B D E H I C F G

중위 순회-왼쪽 자식 노드, 부모 노드, 오른쪽 노드 순으로 방문한다.(LVR)

  1. 현재 노드 n의 왼쪽 서브 트리로 이동한다.->L
  2. 현재 노드 n을 방문하여 처리한다. ->V
  3. 현재 노드 n의 오른쪽 서브 트리로 이동한다.->R
//중위순회
package test3;

public class test2 {
	static char[] arr;
	static int n;
	
	public static void main(String[] args) {
		arr=new char[] {'\u0000','A','B','C','D','E','F','G','\u0000','\u0000','H','I'};
		n=arr.length;
		traverse(1);//1번 노드부터 순회 시작, 1번 노드부터 스택에 올리기.
	}

	private static void traverse(int i) {//i번째 노드의 순회
		if (i<=n-1) {
				//L : 왼쪽 트리로 탐색 이어나감
				traverse(i*2);
				//V: 자기 자신을 방문 처리
				if (arr[i]!='\u0000') {
					System.out.print(arr[i]+" ");
				//R : 오른쪽 트리로 탐색 이어나감
				traverse(i*2+1);
			}
		}
	}
	
}
//
D B H E I A F C G

후위 순회-자식 노드를 좌우 순서로 방문한 후, 부모 노드로 방문(LRV)

  1. 현재 노드 n의 왼쪽 서브 트리로 이동한다.->L
  2. 현재 노드 n의 오른쪽 서브 트리로 이동한다.->R
  3. 현재 노드 n을 방문하여 처리한다. ->V
//후위순회
package test3;

public class test3 {
	static char[] arr;
	static int n;
	
	public static void main(String[] args) {
		arr=new char[] {'\u0000','A','B','C','D','E','F','G','\u0000','\u0000','H','I'};
		n=arr.length;
		traverse(1);//1번 노드부터 순회 시작, 1번 노드부터 스택에 올리기.
	}

	private static void traverse(int i) {//i번째 노드의 순회
		if (i<=n-1) {
				//L : 왼쪽 트리로 탐색 이어나감
				traverse(i*2);
				//R : 오른쪽 트리로 탐색 이어나감
				traverse(i*2+1);
				//V: 자기 자신을 방문 처리
				if (arr[i]!='\u0000') {
					System.out.print(arr[i]+" ");
			}
		}
	}
	
}
//
D H I E B F G C A