자료구조의 4가지 기본 연산

접근, 삽입, 삭제, 검색의 '시간복잡도'와 '공간 복잡도'

1. Graph

노드(정점)과 간선(노드와 노드를 연결하는)으로 구성되어있다.

최대 간선 수

무방향 그래프: n(n-1)/2
방향 그래프: n(n-1)

진입차수 / 진출차수

진입차수: 외부에서 노드로 향하는 간선의 수
진출차수: 노드에서 외부로 향하는 간선의 수

인접 행렬 방식 vs 인접 리스트 방식

1. 인접 행렬

그래프의 연결 관계를 이차원 배열로 나타낸 방식
그래프에 간선이 많이 존재하는 밀집 그래프에 용이
간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요

adj[i][j]: 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

2. 인접 리스트

각각의 노드에 인접한 노드들을 리스트로 표시하는 방식
배열이나 연결 리스트로 구현 가능
연결된 간선의 정보만을 저장한다.

	인접 행렬	인접리스트
장점	구현이 쉽다. 두 노드의 연결여부를 확인하는 시간이 짧다.(O(1)) 간선의 추가와 삭제가 빈번히 일어나는 경우에 효율적이다.	정점의 추가 및 삭제가 빈번히 일어나는 경우 효율적이다. 간선의 정보만을 저장하여 공간 효율성이 우수하다.(O(E))
단점	노드에 연결된 모든 노드들을 조회할 때 시간이(O(V)) 오래 걸린다.	각 노드들의 연결 여부 확인이 오래 걸린다. (O(V))

nodes = {
  0: [1,2],
  1: [0],
  2: [0]
}

2. Tree

노드로 구성된 계층적 자료구조
루트 노드의 child 의 child 에 또 child 추가...
노드(node) 트리의 구성요소
루트(root) 트리 최상위의 노드
depth 루트를 기준으로, 다른 노드로 접근하기 위한 거리
edge 노드와 노드를 잇는 선
leaf 자식이 없는 노드
sibling 같은 부모를 가지면서 같은 depth에 존재하는 노드들의 관계

depth와 height의 차이점

3. Binary Search Tree

모든 노드가 최대 2개의 자식만 갖는 트리
노드의 값이 정렬 방법에 따라 순서가 존재
노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재

이진 탐색 트리 순회 방법

• 전위 순회: 부모 ➣ 좌 ➣ 우
• 중위 순회: 좌 ➣ 부모 ➣ 우
• 후위 순회: 좌 ➣ 우 ➣ 부모

깊이 우선 탐색(DFS, Depth-First Search)

• 우선순위: 자식노드
  Root-> 첫 번째 자식 노드-> 그 자식의 자식 노드...-> Root의 n번째 자식 노드 순회

너비 우선 탐색(BFS, Breadth-First Search)

• 우선순위가 계층
  Root-> 그 다음 자식 노드들을 모두 순회 -> 하위 자식 노드가 있는 층으로 내려가서 자식 노드들을 순회

이진 탐색 트리의 유형

정 이진 트리(Full Binary Tree)

각 내부 노드가 두 개의 자식 노드를 갖는 트리
홀수 개의 자식 노드를 가질 수 없다.

완전 이진 트리(Complete Binary Tree)

부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리
마지막 레벨을 제외하고 모든 노드가 채워져있어야한다.
마지막 레벨의 노드도 왼쪽부터 채워져야한다.

포화 이진 트리(Perfect Binary Tree)

모든 레벨이 가득 채워져 있는 트리
모든 리프 노드의 레벨이 동일하다.

어떻게 구현할 지 생각해보자

1) 무방향 그래프(인접 리스트 방식)

• 노드 추가

this.nodes[node] = this.nodes[node] || [];

• 두 노드 사이에 간선 추가

  1. 첫번째 노드(fromNode)와 두 번째 노드(toNode)를 매개변수로 받는다.
  2. fromNode가 인접한 노드들을 모아둔 배열에 toNode를 넣는다.
  3. toNode가 인접한 노드들을 모아둔 배열에 fromNode 를 넣는다.

• 노드 삭제

  1. 매개변수는 삭제하려는 노드
     2

if (this.nodes[node]) {
  delete this.nodes[node];
}

• 두 노드 사이의 간선 삭제
• 두 노드 사이의 간선 존재 여부 확인
• 그래프에 해당 노드의 존재 여부 확인

2) 트리

• 노드 추가
• 해당 노드의 존재 여부 확인

3) 이진 탐색 트리

• 노드 추가
• 해당 노드의 존재 여부 확인
• 중위 순회

더 공부할 것

이진 탐색 트리에서 노드의 추가, 삭제, 조회의 시간 복잡도

비트 연산자