1. 기본 정리

• 선형 구조 : 자료를 구성하는 데이터들이 순차적으로 나열시킨 형태 -> Queue, Stack
• 비선형 구조 : 데이터가 계층적 혹은 망으로 구성 -> Tree
  선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있음
• Tree : 계층구조 데이터 쉽게 표현 가능 -> 이진탐색트리, 균형트리(AVL트리, red-block트리), 이진 힙(최소/최대 힙)
• Heap : 최대값, 최소값 쉽게 뽑을 수 있음
• BFS : Breadth First Search -> 너비우선
• DFS : Depth First Search -> 깊이 우선
• DP : Dynamic Programming : 동적계획법은 부분문제의 해를 통해 전체 문제를 해결하는 방법
  
  

2. 트리

• 트리의 구성

                A
       B                C
  D         E       F <---> G
H   I     J          sliding


A : Root

D, H, I를 묶어서 sub-tree

D, H, I 안에서 D는 부모노드, H, I는 자식노드

F 는 Leaf 노드

• 이진(binary)트리 : 각 노드가 최대 2개의 자식을 가짐. 하위노드는 무조건 0, 1, 2개

이진트리 X
        o			Level 0
   o    o     o		Level 1
 o      o       o	Level 2


이진트리 O
        o			Level 0
    o       o		Level 1
 o    o   o	        Level 2

• 완전이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입

이진트리 O, 완전이진트리 X
        o			Level 0
    o       o		Level 1
      o   o	        Level 2


이진트리 O, 완전이진트리 O
        o			Level 0
    o       o		Level 1
 o    o   o	        Level 2