📖 Tree 1

• 선형 자료구조 : 배열, 스택, 큐, 연결리스트

1. 1:1로 연결 -> 이전 & 다음
2. 논리적인 시작과 끝

=> 일직선상에 놓일 수 있다.

but> 트리 : 비선형 => 1:N

📌 트리

✅ 트리의 개념

• 비선형 구조

• 원소들 간에 1:N 관계를 가짐 (여기서 1은 항상 부모, N은 항상 자식)

• 원소들 간에 계층관계를 가지는 계층형 자료구조

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

✅ 트리의 조건

1. 부모와 자식이 1 : N

2. 하나의 자식은 둘 이상의 부모 X

3. 노드 개수 : N => 간선 개수 : N-1

4. 원소가 하나이거나 비어있어도 트리

5. 사이클 X

✅ 트리의 정의

• 한 개 이상의 노드로 이루어진 유한 집합이며, 다음 조건을 만족한다. (빈 원소드 트리긴 함)

  • 노드 중 최상위 노드를 루트(root)라 한다.

  • 나머지 노드들은 n(>= 0)개의 분리 집합 T1...TN으로 분리될 수 있다.

    • 간선을 끊을 수 있음

      
      
• 이들 T1, ..., TN은 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리(subtree)라 한다.

단말 노드 : leaf node (external node)

• 자식이 없다

internal node : 자식이 하나 이상

✅ 트리 - 용어 정리

• 노드(node) : 트리의 원소 (vertex)

  • 트리 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

• 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

• 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들

  • B의 자손 노드 - E, F, K

노드 A~A 거리 : 0 => 레벨 : 0
B, C, D : 루트에서 거리가 1 => 레벨 : 1

• 차수 (degree)
  • 노드의 차수 : 노드에 연결된 자식 노드의 수
  • 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값
  • 단말 노드(리프 노드) : 차수가 0인 노드 (자식이 없는 노드)
• 높이(height), 깊이(depth),레벨(level) : 이거 ppt 자료 이상함. 높이가 아니라 깊이로 확인하셈 (인터넷으로 나중에 따로 공부 ㄱ)
  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  • 트리의 높이 : 트리에 있는 노드의 높이 중 가장 큰 값. 최대 레벨

📌 이진트리

✅ 이진트리

• 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리

• 각 노드가 자식 노드를 >최대 2개까지만 가질 수 있는 트리

  • 왼쪽 자식 노드(left child node)
  • 오른쪽 자식 노드(right child node)

• 레벨 i에서의 노드의 최대 개수는 2^i개

• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개, 최대 개수는 (2^(h+1) - 1)개

✅ 포화 이진 트리 (Perfect Binary Tree)

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

✅ 완전 이진 트리 (Complete Binary Tree)

• 높이가 h이고 노드 수가 n개일 때 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

1. 마지막 레벨은 차있어도 되고, 안차있어도 됨.

2. 마지막 레벨 빼고는 모든 레벨이 다 차있어야 함.

완전 이진트리 안에 포화 이진트리가 있음

✅ 편향 이진 트리 (Skewed Binary Tree)

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

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

• 이진 트리에 각 노드 번호를 다음과 같이 부여

• 루트의 번호를 1로 함

• 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n부터 2^(n+1) - 1까지 번호를 차례로 부여

• 노드 번호의 성질

  • 노드 번호가 i인 노드의 부모 노드 번호? i/2
  • 노드 번호가 i인 노드의 왼쪽 자식 노드 번호? 2*i
    - 노드 번호가 i인 노드의 오른쪽 자식 노드 번호? 2-i+1
  • 레벨 n의 노드 번호 시작 번호는? 2^n

• 노드 번호를 배열의 인덱스로 사용

• 높이가 h인 이진 트리를 위한 배열의 크기 : 2^(h+1)

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

• 편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생

• 트리의 중간에 새 노드를 삽입하거나 기존 노드를 삭제할 경우 배열의 크기 변경이 어려워 비효율적이다.

✅ 트리의 표현 - 연결리스트

• 배열을 이용한 이진 트리의 표현의 단점을 보완하기 위해 연결리스트를 이용하여 트리를 표현할 수 있다.

• 연결 자료구조를 이용한 이진 트리의 표현

  • 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

✅ 이진트리 - 순회 (traversal)

• 순회 : 트리의 각 노드를 중복되지 않게 전부 방문하는 것
  • 트리는 비 선형 구조이기에 선형구조에서와 같이 선후 연결 관계를 알 수가 없다
    => 특별한 방법 필요
• 전위 순회 (preorder traversal) : VLR
  • 부모 노드 방문 호, 자식 노드를 좌, 우 순서로 방문
• 중위 순회 (inorder traversal) : LVR
  • 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 방문
• 후위 순회 (postorder traversal) : LRV
  • 자식 노드를 좌우 순서로 방문한 후, 부모 노드로 방문

✅ 전위 순회 (preorder traversal)

• 수행 방법
  • 현재 노드 n을 방문하여 처리한다 -> V
  • 현재 노드 n의 왼쪽 서브 트리로 이동한다 -> L
  • 현재 노드 n의 오른쪽 서브 트리로 이동한다 -> R

preorder_traverse(T) {
	if(T is not null) {
    	visit(T)
        preorder_traverse(T.left)
        preorder_traverse(T.right)
    }
}

✅ 중위 순회 (inorder traversal)

• 수행 방법
  • 현재 노드 n의 왼쪽 서브 트리로 이동한다 : L
  • 현재 노드 n을 방문하여 처리한다 : V
  • 현재 노드 n의 오른쪽 서브 트리로 이동한다 : R

inorder_traverse(T) {
	if(T is not null) {
    	inorder_traverse(T.left)
        visit(T)
        inorder_traverse(T.right)
    }
}

✅ 후위 순회 (postifx traversal)

• 수행 방법
  • 현재 노드 n의 왼쪽 서브 트리로 이동 : L
  • 현재 노드 n의 오른쪽 서브 트리로 이동 R
  • 현재 노드 n 방문하여 처리 : V

postorder_traverse(T) {
	if(T is not null) {
    	postorder_traverse(T.left)
        postorder_traverse(T.right)
        visit(T)
    }
}