알고리즘 - 트리

이상해씨·2022년 8월 8일
0

웹 풀스택(JAVA)

목록 보기
22/54

✔ 트리

  • 트리의 개념
    • 비선형 구조
    • 원소들 간에 1:n 관계를 가지는 자료구조
    • 원소들 간에 계층 관계를 가지는 계층형 자료구조
    • 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조
  • 정의 : 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건 만족.
    1. 노드 중 최상위 노드를 루트(root)라 한다.
    2. 나머지 노드들은 n( >= 0)개의 분리 집합 T1, ... Tn으로 분리될 수 있다.
    3. 각각의 분리 집합은 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(Sub Tree).

트리는 그래프의 한 유형으로 사이클이 없는 그래프.

  • 트리의 용어
    • 노드(node) : 트리의 원소.
    • 간선(edge) : 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드 연결.
    • 루트 노드(root node) : 트리의 시작 노드인 최상위 노드.
    • 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들.
    • 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들.
    • 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들.
    • 서브 트리(Sub Tree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리.
    • 차수(degree)
      • 노드의 차수 : 노드에 연결된 자식 노드의 수.
      • 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값.
      • 달만 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드.
    • 높이
      • 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨.
      • 트리의 높이 : 트리에 있는 노드의 높이 중 가장 큰 값. 최대 레벨.

◾비선형 자료구조 완전 탐색 : BFS/DFS 알고리즘.

1. 이진 트리

  • 이진 트리 : 차수가 2인 트리
    • 각 노드가 자식 노드를 최대 2개 가질 수 있는 트리
      • 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node)
    • 모든 노드들이 최대 2개의 서브 트리를 갖는 특별한 형태의 트리.
  • 이진 트리 특성
    • 높이 i에서 노드의 최대 개수는 2i개
    • 높이 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개, 최대 개수는 2h+1 - 1 개
  • 이진 트리 종류 : 포화 이진 트리, 완전 이진 트리, 편향 이진 트리

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

  • 모든 레벨에 노드가 포화 상태인 이진 트리.
  • 높이가 h일 때, 최대 노드 개수인 2h+1 - 1 의 노드를 가진 이진 트리.
  • 루트를 1번으로 왼쪽부터 차례로 정해진 위치에 대한 노드 번호를 가짐.

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

  • 높이가 h이고 노드 수가 n개일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리.
  • Heap에서 쓰이는 구조.

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

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

◾이진 트리의 표현

  • 배열을 이용한 이진 트리의 표현.
    • 레벨 n에 있는 노드에 대하여 왼쪽부터 번호 차례로 부여.
    • 루트 번호 1.
      • 노드 번호가 i인 노드의 부모 노드 : i/2
      • 노드 번호가 i인 노드의 왼쪽 자식 노드 : 2*i
      • 노드 번호가 i인 노드의 오른쪽 자식 노드 : 2*i+1
      • 레벨 n의 노드 번호 시작 번호 : 2n

비선형 자료구조 완전 탐색

비선형 구조인 트리, 그래프의 각 노드(정점)을 중복되지 않게 방문하는 것.

  • 비선형 구조의 탐색
    • 너비 우선 탐색(Breadth First Search, BFS)
    • 깊이 우선 탐색(Depth First Search, DFS)

2. BFS 알고리즘

  • 너비 우선 탐색 : 루트 노드의 자식 노드들을 모두 차례로 방문한 후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식. (완전 탐색.)
    • 너비 : 각 노드에서의 높이(루트에서 자신까지 사용되는 간선 수)
    • 노드의 높이가 낮은 순서대로 탐색
    • 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행.
    • 선입 선출 형태의 자료구조인 큐를 활용.
void BFS(){
	Queue<T> q = new Queue<T>();
    q.offer(root);
    while (!q.isEmpty()){
    	T data = q.poll();
        // data 방문
        for (data와 연결된 모든 간선){
        	q.offer(data의 자식 노드);
        }
    }
}

큐를 스택으로 전환한다면? : 동일한 구조로 DFS 알고리즘 구현 가능.

3. DFS 알고리즘

  • 깊이 우선 탐색 : 루트 노드에서 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색. 더이상 갈 곳이 없으면 이전 갈림길로 돌아가 다른 방향으로 탐색. (완전 탐색.)
    • 후입 선출 형태의 자료구조인 스택을 활용
// 재귀적 표현
void DFS(v){
	// v 방문
    for(v의 모든 자식 노드 w){
    	DFS(w);
    }
}
profile
후라이드 치킨

0개의 댓글