Tree

• 트리는 노드로 구성된 계층적 자료구조입니다.
• 트리는 하나의 루트 노드를 갖습니다.
  • 그림에서 2가 루트 노드
• 루트 노드는 0개 이상의 자식 노드를 갖습니다.
  • 2의 자식 노드는 7, 5
  • 자식 노드 또한 0개 이상의 자식 노드를 갖고 있습니다.
    • 7(부모 노드)의 자식 노드는 2, 10, 6
• 루트 노드를 기준으로 다른 노드로 접근하기 위한 거리를 Depth라고 합니다.
  • depth 0 : 2, depth 1 : 7, 5 ...
• 같은 부모에 같은 depth에 존재하는 노드들은 Sibling(형제) 관계라 합니다.
  • 7의 자식 노드 2, 10 ,6 은 Sibling 관계
• 노드들과 노드들은 간선(Edge)로 연결되어 있습니다.
• 자식이 없는 노드들은 leaf 라고 합니다.
  • 5, 11, 4
• 트리의 특정 깊이를 가지는 노드이 집합을 Level이라 합니다.
  • 11의 Level : 4

Depth vs Height

• Depth는 루트에서 특정 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말합니다.
  • 6의 Depth : 2
  • 11의 Depth : 3
• Heigth는 루트 노드에서 가장 밑에 있는 노드의 깊이를 말힙니다.
  • 3

BST(Binary Search Tree)

• 자식 노드가 최대 2개를 가진 트리는 Binary Tree입니다.
• Binary Search Tree는 노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값이 존재하고, 오른쪽 서브 트리에는 노드의 값보다 큰 값이 존재합니다.

Tree의 종류

Complete Binary Tree

• Level 별(마지막 레벨은 제외)로 왼쪽으로 채워진 트리를 Complete Binary Tree입니다.

Full Binary Tree

• 자식이 아예 없거나, 자식이 2개 전부 있다면 Full Binary Tree입니다.

Perfect Binary Tree

• 모든 노드가 2개의 자식을 가지고 깊이와 레벨이 같은 트리를 Perfect Binary Tree라고 합니다.

Tree Traversals

Inorder (Left → Root → Right)

1 → 3 → 4 → 6 → 7 → 8 → 13 → 14 → 10

Preorder (Root → Left → Right)

8 → 3 → 1 → 6 → 4 → 7 → 10 → 14 → 13

Postorder (Left → Right → Root)

1 → 4 → 7 → 6 → 3 → 13 → 14 → 10 → 8

Graph

• 그래프는 노드(또는 Vertex)와 노드와 노드를 연결하는 간선(Edge)으로 구성됩니다.
• 그래프는 방향(비대칭)을 가질 수 있고, 무방향(대칭)일 수 있습니다.

Adjacent Array, Adjacent List

Adjacent Array

• Adjacent Array는 노드의 개수 만큼 N * N 행렬에 Boolean으로 저장된다.
• 간선의 수와 상관없이 항상 N^2개의 메모리 공간이 필요하다.
• 인접한 노드를 찾기 위해서는 존재하는 노드를 전부 순회해야 한다.

Adjacent List

• 그래프를 표현하는 가장 일반적인 방법이다.
• 모든 노드를 인접 리스트에 저장한다.
  • 각 노드를 기준으로 인접한 노드를 리스트에 저장한다.

Adjacent(인접)

• 위 그림을 예로, 6과 4 노드 사이에 간선이 있을 때 6과 4는 서로 인접한다고 할 수 있습니다.

In degree, Out degree

• 자신의 노드로 들어오는 간선의 수 : In degree
• 자신의 노드에서 나가는 간선의 수 : Out degree