[이산수학] 트리

Joy·2020년 10월 28일
0

Math

목록 보기
11/15

ref : http://www.kocw.net/home/search/kemView.do?kemId=1335653

  • 트리
    노드, 루트, 부모 자식 형제, 리프 중간, 조상 자손
    서브, 차수, 레벨, 트리의 높이, 포레스트

  • 트리에 관한 정리
    n개의 노드를 갖는 트리의 모서리 수 n-1
    트리에서 모서리 제거하면 연결그래프가 아님
    녿 u에서 v로의 유일한 경로가 ㅈ존재

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

  • 이진 트리 구현
    레벨 k 최대 노드 수 => 2**k
    높이가 m 최대 노드 수 2**
    m+1
    최소 노드수 m+1

  • 이진트리 구현
    배열, 연결 리스트

  • 이진트리 순회
    전위, 중위, 후위

  • 이진 탐색 트리
    노드가 가지고 있는 데이터에 따라 노드의 위치를 탐색

  • 트리의 활용
    최소 신장 트리(prim, kruscal), 허프만 알고리즘


1. 트리의 개념

* Tree 트리

트리의 예시



Node 노드


꼭지점 모두.

Root 루트

  • 절대적임.

+ Parent & Child node 부모노드, 자식노드

Silbling node 형제노드

  • 같은 단게예 있고 부모가 같은 노드들

leaf node 리프노드

internal node 중간노드

Ancester node 조상노드

  • 루트에서 한 노트로 가는 동안 있는 모든 노드

Descendant Node 자손노드

  • 조상과는 반대로 리프 노드를 제외한 모든 노드가 자손노드를 가짐.

sub tree 서브트리



degree 차수

  • 자손 descendant 노드 아니구 자식 child 노드다!!!

Level 레벨

  • 루트는 레벨 0!!!

레벨 예시



Height = Depth = 높이 깊이



Forest 포레스트

  • 루트랑 가지 제거!



트리 예제



Node edge 정리


트리에 대한 정리





2. 이진트리

Binary Tree 이진트리

  • 이진트리에서 노드가 왼쪽에 있는거랑 오른쪽에 잇는거 구분

이진트리의 서브트리:


Complete Binary Tree 완전이진트리

완전이진트리 판별 :


Full binary tree =포화이진트리

포화이진트리 예시:


Skewed Binary tree 편향이진트리

  • 한쪽에만 치우침


이진트리 예제:



이진트리와 노드

  • 레벨 0은 루트노드라 노드수는 2의 0승 = 1
  • 높이=깊이=최대 레벨
  • 증명은 수학적 귀납으로 가능



이진트리 구현: 배열 / 연결리스트 + 포인터

1. 배열로 구현


index of node 노드인덱스


편향이진트리 배열로 구현 :

  • 비효율적이다!


2. 연결리스트로 구현 + 포인터

연결리스트로 구현 예시:




이진트리의 순회


Preorder Traversal = 전위순회

preorder traversal 예시 :



Inorder Traversal 중위순회

중위순회 예시:



Postorder Traversal 후위순회

후위순회예시:






이진트리 순회를 이용한 수식 표현



3. 트리의 활용

최소신장트리, 허프만코드

Spanning Tree 신장트리

  • node는 다 포함!!

그래프 G와 시장트리 예시


Minimal spanning tree

  • 이에 사용하는 알고리즘 두 개 있음 :


+ Prim Algorithm 프림 알고리즘

  • 순환은 안되게 선택해라!

예시:


+ Kruscal Algorithm 크루스칼 알고리즘

  • 프림은 한개만 선택하지만 크루스칼은 여러개가 있으면 모두동시에 선택함.

예시

--> 모양은 다를 수 잇으나 비용 결과같은 프림과 같음



Huffman code 허프만코드

huffman algorithm

예시:


  • -



profile
roundy

0개의 댓글