인공기초 - 0605

트리 구조

트리는 비선형 자료구조로 계층적 관계를 표현한다.

트리 구조

 

• 루트 노드 (root node)
  • 트리의 맨 꼭대기 노드
• 단말 노드 (leaf node)
  • 자식이 없는 노드, '단 노드' 또는 '잎 노드', 차수가 0인 노드
• 간선 (edge)
  • 노드를 연결하는 선 (link, branch)
• 부모노드 (Parent Node)
  • 자신을 파생시킨 한 레벨 위의 노드
• 자식노드 (Child Node)
  • 자신이 파생시킨 한 레벨 아래의 노드
• 형제노드 (sibling Node)
  • 부모가 같은 노드
• 깊이 (Depth)
  • 루트에세 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 레벨 (level)
  • 루트노드의 레벨을 1로 가정한 후 자식으로 내려갈수록 1씩 증가
• 노드의 차수 (degree)
  • 하위 트리 개수, 각 노드가 가진 가지의 수
• 트리의 차수
  • 각 노드의 차수 중 최댓값

 

 

트리 탐색 방법

무정보 탐색 - 무차별 탐색, 맹목적 탐색

상태 공간에 내재된 정보와 상관없이 모든 상태를 규칙에 따라 탐색하는 방법이다.

 

• 깊이 우선 탐색
  
  • 탐색 트리에서 길이 있는 한 앞으로 계속 전진하여 탐색하는 방법
  • 분기점에 도착했을 때 방문하지 않은 곳을 골라 앞으로 나아가며 목표에 도달
• 너비 우선 탐색
  • 트리를 탐색하다 분기점에 도착했을 때, 동일한 깊이의 상태 공간을 모두 방문하는 방법
  • 목표 지점에 도착할 때까지 가로 방향으로 나아감

 

트리 탐색 방법

 

• 깊이 우선 탐색
  
  • a -> b -> d -> g -> e -> h -> i -> c -> f
• 너비 우선 탐색
  • a -> b -> c -> d -> e -> f -> g -> h -> i
    
    

 

 

• bfs (breadth first search)
  • 1 -> 2 -> 3 -> 4 -> 5
• dfs (depth first search)
  • 1 -> 2 -> 4 -> 5 -> 3 
  • Pre-order
    • 1 -> 2 -> 4 -> 5 -> 3
  • In-order
    • 4 -> 2 -> 5 -> 1 -> 3
  • Post-order
    • 4 -> 5 -> 2 -> 3 -> 1

 

 

 

 

2024.06.04 - [인공지능 기초] - 인공기초 - 0604

인공기초 - 0604