[알고리즘 기초] 07_Tree / Python

[알고리즘 기초] 07_Tree / Python

[알고리즘 기초] 07_Tree / Python

Tree

• 트리의 개념
  • 비선형 구조
  • 원소들 간에 1:n 관계를 가지는 자료구조
  • 원소들 간에 계층 관계를 가지는 계층형 자료구조
  • 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조
• 트리의 정의
  • 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다
    1. 노드 중 최상위 노드를 root 라 한다.
    2. 나머지 노드들은 n(>=0) 개의 분리 집합 T1, ..., TN 으로 분리될 수 있다.
  • 이들 T1, ..., TN 은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리 (subtree)라 한다.
• 트리의 용어
  • 노드(node) - 트리의 원소
  • 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
  • 루트 노드(root node) - 트리의 시작 노드
  • 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들
  • 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
  • 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
  • 자손 노드 - 서브 트리에 있는 하위 레벨의 노드들
  • 차수(degree)
    • 노드의 차수 : 노드에 연결된 자식 노드의 수
    • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
    • 단말 도느(리프 노트) : 차수가 0인 노드. 자식 노드가 없는 노드
  • 높이
    • 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨( 내려 갈 수로 값이 증가 depth)
    • 트리의 높이 : 트리에 있느 노드의 높이 중에서 가장 큰 값, 최대 레벨
  • 넓이 - 전체 트리의 레벨 별 최대 node의 수

 

이진 트리

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

 

이진 트리 - 종류

• 포화 이진 트리(Full Binary Tree)
  • 모든 레벨에 노드가 포화상태로 차 있는 이진트리
  • 높이가 h일때, 최대의 노드 개수의 노드를 가진 이진트리
  • 루트를 1번으로 하여 마지막 노드까지 정해진 위치에 대한 노드 번호를 가짐
• 완전 이진 트리(Complete Binary Tree)
  • 높이가 h이고 노드 수가 n개 일때(단, h+1 <= n < 2**(h+1)-1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진트리
• 평향 이진 트리(Skewed Bianry Tree)
  • 높이 h에 대한 최소 노드의 개수를 가지면서 한쪽 방향의 자식 노드만을 가진 이진트리
    • 왼쪽 편향 이진트리
    • 오른쪽 편향 이진트리

 

이진트리 - 순회(trabersal)

• 순회란 트리이ㅡ 각 노드를 중복되지 않게 전부 방문하는 방법
• 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없다.
• 기본적인 순회 방법 (V: 루트, L:왼쪽 서브트리, R:오른쪽 서브 트리)
  • 전위순회 : VLR
  • 중위순회 : LVR
  • 후위순회 : LRV

 

이진트리의 표현 - 배열

• 이진 트리에 각 노드 번호를 다음과 같이 부여
• 루트의 번호를 1로 함
• 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n 부터 2^(n+1) - 1 까지의 번호를 차례로 부여
• 노트 번호의 성질
  • 노드 번호가 i인 노드의 부모 노트 번호? i/2
  • 노드 번호가 i인 노드의 왼쪽 자식 노드 번호? 2*i
  • 노브 번호가 i인 노드의 오른쪽 자식 노드 번호? 2*i + 1
  • 레벨 n의 노드 번호 시작 번호는? 2^n
• 단점
  • 편향 이진 트리의 겨우엥 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
  • 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기변경이 어려워 비효율적

 

이진트리의 표현 - 연결 리스트

• 배열을 이용한 이진 트리의 표현의 단점을 보완하기 위해 연결리스트를 이용하여 트리를 표현할 수 있다.
• 연결 자료구조를 이용한 이진트리의 표현
  • 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현
  left.                                                                              data                                                                 right

  왼쪽 자식 노드

  오른쪽 자식 노드

 

수식트리

• 수식을 표현하는 이진트리
• 연산자는 루트 노드이거나 가지노드
• 피연산자는 모두 잎 노드
• 중위 순회 : A/B*C+D+E - 중위표기법
• 후위 순회 : AB/C*D+E+ - 후위표기법
• 전위 순회: +**/ABCDE - 전위 표기법

 

이진 탐색 트리

• 탐색작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 갖는다.
• key(왼쪽 서브 트리)<key(루트 노드)<key(오른쪽 서브 트리)
• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다.
• 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

 

이진 탐색 트리 - 연산

• 루트에서 시작
• 탐색할 키 값을 루트 노드의 키값과 비교한다.
• 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.