Tree 알고리즘

트리(Tree) 알고리즘🌳

1️⃣ 트리란?

• 1:n의 관계를 가지는 비선형 구조
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 한 개 이상의 노드로 이루어진 유한 집합

2️⃣ 용어

• 노드(node) : 트리의 원소
• 루트노드(Root) : 최상위 노드, 트리의 시작
• 간선 : 노드를 연결하는 선 ex) 부모노드와 자식노드 연결
• 형제 노드 : 같은 부모 노드를 가진 자식 노드들
• 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들
• 노드의 차수 : 노드에 연결된 자식 노드의 수
• 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값
• 단말 노드(Leaf) : 차수가 0인 노드 (자식노드가 없는 노드)
• 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
• 트리의 높이 : 트리에 있는 노드의 높이 중 가장 큰 값, 최대 레벨

3️⃣ 이진 트리

• 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대 2개까지만 가질 수 있음 (왼쪽 자식, 오른쪽 자식)
• 레벨 i에서의 노드의 최대 개수 = 2\i**개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 2\(h+1)-1개**
  if h == 0 : 가질 수 있는 노드의 최소 개수는 1개, 최대 개수는 1개
  if h == 1 : 가질 수 있는 노드의 최소 개수는 2개, 최대 개수는 3개

3️⃣-1️⃣. 포화이진트리

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

3️⃣-2️⃣. 완전이진트리

• 높이가 h이고 노드 수가 n일 때 (단, h+1 <= n <= 2(h+1)-1), 포화 이진 트리의 **노드번호 1번부터 n번까지 빈 자리가 없는 트리
• 포화이진트리보다 꽉 차있진 않으나 빈 곳이 없는 트리

3️⃣-3️⃣. 순회

• 트리의 노드들을 체계적으로 방문하는 것

전위순회 (Preorder)

def preorder_travers(T):
    if T : T is not None
        visit(T)
        preorder_travers(T.left)
        preorder_travers(T.right)

중위순회 (Inorder)

def inorder_travers(T):
    if T :
        inorder_travers(T.left)
        visit(T):
        inorder_travers(T.right)

후위순회(Postorder)

def postorder_travers(T):
    if T:
        postorder_travers(T.left)
        postorder_travers(T.right)
        visit(T)

3️⃣-4️⃣. 배열을 통한 이진트리의 표현

• 노드 번호의 성질

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

• 부모 번호를 인덱스로 자식을 저장

# 전위 순회
def pre_order(v):
    if v: # 0번 정점이 없으므로, 0번은 자식이 없는 경우를 표시
        print(v)
        pre_order(child1[v])
        pre_order(child2[v])

# 중위 순회
def in_order(v):
    if v:
        in_order(child1[v])
        print(v)
        in_order(child2[v])

# 후위 순회
def post_order(v):
    if v:
        post_order(child1[v])
        post_order(child2[v])
        print(v)

E = int(input()) # 간선의 개수
arr = list(map(int, input().split()))
V = E+1 # 정점의 개수 (간선 + 1), 정점 수 == 1번부터 V번까지 정점이 있을 때 마지막 정점

# 부모 번호를 인덱스로 자식번호 저장
child1 = [0]*(V+1)
child2 = [0]*(V+1)

for i in range(E):
    parents, child = arr[i*2], arr[i*2+1]
    if child1[parents] == 0:
        child1[parents] = child
    else:
        child2[parents] = child

pre_order(1)
in_order(1)
post_order(1)

• 자식 번호를 인덱스로 부모 번호를 저장

E = int(input()) # 간선의 개수
arr = list(map(int, input().split()))
V = E+1

par = [0]*(V+1)
for i in range(E):
    p, c = arr[i*2], arr[i*2+1]
    par[c] = p
print(*par)

# root 찾기
for i in range(1, V+1):
    if par[i] == 0:
        root = i
        break
print(root)

# 정점 c의 조상 찾기
c = 1
anc = []
while par[c] != 0:
    anc.append(par[c])
    c = par[c]
print(*anc)

• 배열을 이용한 이진트리 표현의 단점
  • 편향 이진 트리의 경우, 사용하지 않는 배열 원소에 대한 메모리 공간 낭비가 발생
  • 트리 중간에 새로운 노드를 삽입하거나 기존 노드를 삭제할 경우, 배열의 크기 변경이 어려워 비효율적

• 보완 → 연결리스트를 이용하여 트리 표현

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

3️⃣-5️⃣. 수식트리

• 수식을 표현하는 이진트리 (수식이진트리)
• 연산자는 루트노드이거나 가지노드
• 피연산자는 모드 잎노드
• 수식트리의 순회

3️⃣-6️⃣. 이진 탐색 트리

• 탐색 작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 가짐
• 왼쪽 서브트리 < 루트 노드 < 오른쪽 서브트리
• 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있음
• 왼쪽 서브트리와 오른쪽 서브트리도 각각 이진 탐색 트리
• 탐색 연산
  • 탐색할 키 값 = x
  • x == root : 원하는 원소를 찾았으므로 탐색연산 성공
  • x < root : 왼쪽 서브트리에 대해 탐색 연산 수행
  • x > root : 오른쪽 서브 트리에 대해 탐색 연산 수행

• 삽입 연산
  • 삽입할 원소와 같은 원소가 트리에 있으면 삽입 불가능 (서로 다른 유일한 키)
  • 탐색을 실패한 위치에 원소를 삽입

• 성능
  • 탐색, 삽입, 삭제 = O(h), h = BTS의 깊이
  • 이진 트리가 균형적으로 생성되어 있는 경우 = O(log n)
  • 한쪽으로 치우친 경사 이진 트리인 경우 = O(n)