오늘의 문제 버블 정렬(toy problem)
버블정렬에 대해 알아보기

Graph

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조.

점은 그래프에서는 정점(vertex)이라고 표현하고, 선은 간선(edge) 이라고 표현

알아둬야 할 그래프 용어들

• 무향그래프(undirected graph) : edge에 방향성이 없어서 연결된 vertex들의 순서가 정해지지 않은 그래프
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지 나타냄
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현

Tree

• 트리란 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이 때 각 노드는 재사용 되지 않는 구조

tree 의 서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 유일하다.
tree 에는 사이클을 가지는 노드 집합이 존재하지 않는다.
tree 반드시 하나의 root가 존재한다. (부모 노드가 존재하지 않는 노드)

• 노드(node) : 트리는 노드들의 집합으로 트리를 구성하는 것으로 보통 (value) 값과 부모 자식의 정보를 가짐
• 엣지(edge) : 엣지는 노드들을 연결하는 간선으로 부모 노드와 자식 노드를 연결
• 루트(root node) : 가장 상위 노드
• 리프(leaf node) : 가장 하위 노드
• 형제 노드 : 같은 부모를 가지는 자식 노드들
• 깊이(depth) : tree에서 부모에서 자식순으로 이동할 때, depth 가 1 증가하며 따라 형제 노드 간의 depth는 일치하며 root node의 depth는 0이된다.

Binary Search Tree

• 이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종
  모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 정의

• 완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
• 정 이진 트리: 각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
• 포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

Tree traversal

전위 순회
0 > 1 > 3 > 7 > 8 > 4 > 9 > 10 > 2 > 5 > 6 > 11
부모노드 > 왼쪽 자식노드 > 오른쪽 자식노드(재귀)
0번 부모노드를 확인하고 왼쪽 자식노드인 1번으로 이동한 뒤 1번이 부모노드가 되서 1번을 확인하고 3번 왼쪽 자식노드로 이동 3번노드가 부모노드가 되서 확인하고 7번 노드로 이동...

중위 순회
7 > 3 > 8 > 1 > 9 > 4 > 10 > 0 > 5 > 2 > 6 > 11
왼쪽 자식노드 > 부모노드 > 오른쪽 자식노드(재귀)
왼쪽 자식노드가 없어질 때 까지 이동해서 확인(7번) 후 왼쪽 자식노드의 부모노드 3번 확인하고 오른쪽 자식노드 8번 확인 후 3번의 부모노드 1번 확인 후 오른쪽 자식노드 4번의 왼쪽자식노드 9번 확인하고 부모노드 4번확인 후 오른쪽 자식노드 10번확인...

후위 순회
7 > 8 > 3 > 9 > 10 > 4 > 1 > 5 > 11 > 6 > 2 > 0
왼쪽 자식노드 > 오른쪽 자식노드 > 부모노드(재귀)
왼쪽 자식노드가 없어질 때 까지 이동해서 확인(7번) 후 부모노드의 오른쪽 자식노드 8번 확인 > 부모노드 3번 확인 > 3번의 부모노드 1번의 오른쪽 자식노드 4번의 왼쪽자식노드 9번 확인 > 4번의 오른쪽자식노드 10번 > 부모노드 4번 > 4번의 부모노드 1번 확인...

깊이 우선 탐색 (DFS, Depth-First Search)
0 > 1 > 3 > 7 > 8 > 4 > 9 > 10 > 2 > 5 > 6 > 11
더이상 깊이 갈 곳이 없을 경우 옆으로 이동
루트부터 왼쪽으로 리프까지 이동

너비 우선 탐색 (BFS, Breadth-First Search)
0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9 > 10 > 11
넓게 이동 후 밑으로 이동