트리

사이클이 없고, 하나의 루트에서 시작하는 계층적 자료구조 이다.

용어 정리

• 노드(Node) : 트리의 기본 단위

• 루트 노드(Root Node) : 트리의 가장 위에 있는 노드

• 부모 노드(Parent Node) : 다른 노드를 가진 노드

• 자식 노드(Child Node) : 부모로부터 파생된 노드

• 단말 노드(Leaf Node) : 자식이 없는 노드

• 간선(Edge) : 노드와 노드를 연결하는 선

• 서브트리(Subtree) : 트리 안의 부분 트리

• 높이(Height) : 트리의 최대길이

• 레벨(Level) : 같은 깊이를 가진 노드들의 집합

• 포화 이진 트리 : 모든 레벨이 꽉 차있는 트리

• 완전 이진 트리 : 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워진 트리

  이진트리 성질

• 간선의 수 = 노드 수 -1

• 높이가 h인 이진트리에서

  • 최대 노드 수 : 2^h - 1

  • 최소 노드 수 : h

  • 자식 두개인 노드의 수 + 1 = 단말노드의 개수

    연결리스트

    기본 연결리스트에서 링크 필드가 왼쪽, 오른쪽 필드로 두개로 구현 가능하다.
    연결리스트인만큼 부모 -> 자식으로만 접근 가능하다.

    불균형한 이진 트리에서도 편리하게 사용 가능하다.

    배열

    인덱스 1부터 값을 삽입한다.

    이 때 부모가 자식으로 접근하려면 부모의 인덱스값 * 2, 부모의 인덱스값 * 2 + 1 로 접근 가능하다.
    자식으로부터 부모로 접근하려면 자식의 인덱스값 // 2 이다.

    균형잡힌 트리에서 부모 자식 간 규칙이 있어 접근이 쉽다.
    불균형한 트리에서 규칙을 유지해야 하기 때문에 메모리가 낭비된다.

    트리 순회

    순회

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

    전위순회

    루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 순회

    코드

    def preorder(tree, index=1):
      if index >= len(tree) or tree[index] is None:
          return
      print(tree[index], end=' ')
      preorder(tree, 2 * index)
      preorder(tree, 2 * index + 1)
    

    중위순회

    왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 순회

    코드

    def preorder(tree, index=1):
       if index >= len(tree) or tree[index] is None:
           return
       preorder(tree, 2 * index)
       print(tree[index], end=' ')
       preorder(tree, 2 * index + 1)

    후위순회

    왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 순회

    코드

    def preorder(tree, index=1):
       if index >= len(tree) or tree[index] is None:
           return
           
       preorder(tree, 2 * index)
       preorder(tree, 2 * index + 1)
       print(tree[index], end=' ')

    레벨순회

    트리의 레벨 순으로 왼쪽에서 오른쪽으로 탐색하는 방식
    큐 자료구조를 이용하여 구현한다.

    from collections import deque 
    
    def bfs(tree):
        queue = deque()     
        queue.append(1)     
    
        while queue:
            index = queue.popleft()  
    
            if index >= len(tree) or tree[index] is None:
                continue
    
            print(tree[index], end=' ')
    
            left = 2 * index
            right = 2 * index + 1
            queue.append(left)
            queue.append(right)
    

    트리 코드

    

해당 트리를 구현하고 모든 순회방법으로 출력하면

from collections import deque  # 큐 사용을 위해 import


def vlr(tree, index=1):
    if index >= len(tree) or tree[index] is None:
        return
    print(tree[index], end=' ')
    vlr(tree, 2 * index)
    vlr(tree, 2 * index + 1)

def lvr(tree, index=1):
  if index >= len(tree) or tree[index] is None:
      return
  lvr(tree, 2 * index)
  print(tree[index], end=' ')
  lvr(tree, 2 * index + 1)

def lrv(tree, index=1):
  if index >= len(tree) or tree[index] is None:
      return
  
  lrv(tree, 2 * index)
  lrv(tree, 2 * index + 1)
  print(tree[index], end=' ')

def bfs(tree):
    queue = deque()     
    queue.append(1)     
    while queue:
        index = queue.popleft()   

        if index >= len(tree) or tree[index] is None:
            continue

        print(tree[index], end=' ')

        left = 2 * index 
        right = 2 * index + 1
        queue.append(left)
        queue.append(right)



tree = [None , 'A', 'B', 'C', 'D', 'E', 'F']

print("\nvlr 탐색 결과:")
vlr(tree)

print("\nlvr 탐색 결과:")
lvr(tree)

print("\nlrv 탐색 결과:")
lrv(tree)

print("\n너비 우선 탐색 결과:")
bfs(tree)

기대한 출력 값을 얻을 수 있다.

트리의 노드 개수

def count(tree, index=1):  
  if (index < len(tree) and not tree[index] is None):
      return 1 + count(tree, index*2) + count(tree, index*2+1)
  return 0

자기 자신의 수 + 왼쪽 서브 트리의 노드 개수 + 오른쪽 서브트리의 노드 개수

트리의 높이

def height(tree, index=1):  
 if (index < len(tree) and not tree[index] is None):
      return 1 + max(height(tree, index * 2), height(tree, index * 2 + 1))
 return 0

자기 자신의 높이 + max(왼쪽 서브 트리의 높이, 오른쪽 서브 트리의 높이)

이진 탐색 트리

노드 값이 왼쪽 서브 < 루트 < 오른쪽 서브

def search(tree, value):
   index=1
   node = tree[index]
   while node is not None:
     if value == node:
       return True
     elif value < node:
       index = index * 2
     else:
       index = index * 2 + 1
     if index >= len(tree):
       break
     node = tree[index] 
   return False

배열로 구현 한 트리에서 tree 배열에 있는 값을 비교하며 값을 찾는다.

이진 탐색 트리 삽입

위 탐색 트리에서 null 을 만나면 False 를 반환하는게 아닌 그 자리에 값을 삽입한다.

이진 탐색 트리 삭제

삭제는 크게 3가지 경우로 나누어 진다.
1. 자식이 없는 단말노드인 경우
2. 자식이 하나있는 경우
3. 자식이 두개 있는 경우

1번 경우
내가 사라져도 다른 노드들에 영향을 미치지 않기 때문에 나만 삭제되면 된다.

2번 경우
내가 사라지면 내가 가르키고 있던 자식이 사라지기 때문에 날 가르키던 부모의 랑크 필드에 내 자식의 주소값을 넣는다.

3번 경우
아무값이나 들어간다면 이진 탐색 트리의 규칙이 파괴된다.
따라서 유효한 값이 들어가야 하는데 이는 나를 포함한 트리에서 인접한 큰, 작은 값 중 하나가 들어가야 한다.
이는 내 기준 오른쪽 서브트리의 최소값(인접한 큰값) 이나 왼쪽 서브트리의 최대값(인접한 작은값) 이다.
내 값과 위 조건에 해당하는 노드의 값을 바꾼 후 삭제하려는 값은 이제 단말노드이기 때문에 그냥 삭제하면 된다.

그래프

정점과 정점들을 연결하는 간선으로 구성된 자료구조

용어 정리

• 정점(Vertex) : 노드(node) 라고도 부르며 데이터가 저장된다.
• 간선(Edge) : 링크(link) 라고도 부르며 정점을 연결하는 선이다.
• 차수(Degree): 정점에 직접 연결된 간선의 개수이다.
• 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프
• 무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프

표현 방법

인접 행렬

정점이 n개라 하면 n*n 의 이차원 배열을 선언하고
i -> j 로 이동 가능한 간선이 존재하면 edge[i][j] 에 1을 삽입, 없으면 0을 삽입한다.

구현이 쉽고 간선이 많은 그래프면 유리하다.
하지만 간선의 개수 상관 없이 n*n 의 배열을 선언하기 때문에 메모리 낭비가 발생한다.

인접 리스트

정점 수 만큼의 배열이 있고 각 정점에서 어떤 정점으로 갈 수 있는 간선이 있는지를 저장한디.

간선 수에 따라서 배열을 선언하기 때문에 메모리 절약이 가능하다.
하지만 간선 존재 여부 확인이 인접 행렬보다 느리다.

그래프 탐색 기법

DFS (깊이 우선 탐색)

한 정점에서 시작하여 갈 수 있는 곳 까지 쭉 들어가며 탐색한다.
더 이상 갈 곳이 없으면 한 단계식 돌아오며 다른경로를 탐색한다.
스택 구조를 활용한다. (재귀, 반복문)

그래프
1 - 2 - 4
|   |
3 - 5

DFS(A) 순서 예시:
1 → 2 → 4 → 5 → 3

graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 5],
    4: [2],
    5: [2, 3]
}

visited = [False] * (len(graph) + 1)  
def dfs(node):
    if visited[node]:
        return
    visited[node] = True
    print(node, end=' ')
    for a in graph[node]:
        dfs(a)

dfs(1)  

기대한 값이 출력된다.

BFS (너비 우선 탐색)

한 정점에서 시작하여 가장 가까운 정점을 전부 방문하며 출력한다.
큐 구조를 사용하여 구현한다.

그래프
1 - 2 - 4
|   |
3 - 5

BFS(A) 순서 예시:
1 → 2 → 3 → 4 → 5

from collections import deque

graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 5],
    4: [2],
    5: [2, 3]
}

visited = [False] * (len(graph) + 1)

def bfs(start):
    queue = deque([start])   
    visited[start] = True    
    
    while queue:
        node = queue.popleft()   
        print(node, end=' ')     
        
        for a in graph[node]:
            if not visited[a]:   
                visited[a] = True
                queue.append(a)  

bfs(1)

기대한 값이 출력된다.