자료구조 Graph, Tree, BST

Graph

• 그래프는 노드, 노드를 연결하는 간선 으로 구성된 자료구조
• 무방향 그래프(양쪽 노드 모두 상대 노드에 접근가능)
• 방향성 그래프(한쪽 노드에서만 상대 노드에 접근가능)
• 진입차수: 해당 노드에 접근할 수 있는 다른 노드의 수
• 진출차수: 해당 노드가 접근할수 있는 다른 노드의 수
• 인접행렬
  • 그래프의 연결관계를 이차원 배열로 나타냄
  • 장점: 구현이 쉽고 두 노드가 연결 되어있는지 확인이 쉽다.O(1)
  • 단점: 한 노드에 연결된 모든 노드들에 방문하고 싶은경우 O(v)의 시간이 걸림
• 인접 리스트
  • 각 노드의 연결관계를 리스트로 나타냄
  • 장점: 간선의 개수에 비례하는 메모리 만을 차지함, 한노드에 연결된 모든 노드들에 방문하고 싶은경우 진출차수만큼의 시간복잡도를 가짐
  • 단점: 두 노드가 연결되어있는지 확인하는데 O(v)만큼의 시간이 걸림

Tree

• 트리구조는 각 노드가 1개의 부모 노드를 가지고 부모는 0개 이상의 자식 노드를 가진 자료구조이다.
• root: 최상위 노드를 말한다
• depth: root를 기준으로 다른 노드에 접근하기위한 거리를 말한다.
• height: tree에서 가장 큰 depth
• sibling: 같은 부모를 가지며 같은 depth를 가진 노드들을 말한다.
• leaf: 자식이 없는 노드를 말한다.

BST(Binary search Tree)

• 최대 2개의 자식만 같는 트리
• 노드의 왼쪽 서브트리에는 부모 노드의 값보다 작은 값이, 오른쪽 서브트리에는 부모 노드의 값보다 같거나 큰값이 존재함
• 깊이 우선 탐색: 해당 노드의 자식노드를 우선 파악한 후 형제노드를 파악하는 방식 
• 너비 우선 탐색: 해당 노드의 형제 노드를 우선 파악한 후 자식노드를 파악하는 방식
• 부모 노드를 파악하는 순서에 따라 전위 순회(부모,좌,우), 중위 순회(좌, 부모, 우), 후위 순회(좌, 우, 부모)로 나뉜다.
• 정 이진 트리: 모든 노드가 0개 혹은 2개의 자식노드를 가진다.
• 완전 이진 트리: 마지막 레벨을 제외한 나머지 노드가 꽉차있어야 하며 마지막 레벨의 노드도 왼쪽부터 채워져야한다.
• 포화 이진 트리: 마지막 레벨을 제외한 모든 노드가 2개의 자식 노드를 가진 이진트리 이다.