[2022/09/04 복습] 헷갈리는 자료구조론 - 트리(힙트리, 이진검색트리), 그래프(방향/무방향, 강력연결요소)

• 전날 공부량: 30문제;;

• 헷갈리는 자료구조론: 헷갈리는 자료구조론 - 트리(힙트리, 이진검색트리), 그래프(방향/무방향, 강력연결요소)

1. 최대힙 원소 삭제 시 구성 방법
   (1) 루트(최댓값) 삭제
   (2) 맨 끝 값을 루트로
   (3) 최대힙트리 재구성
   

2. 이진검색트리
   ▶️탐색, 삽입, 삭제 시간은 O(h)
   (높이 최악인 경우 h = N(사향이진트리)이기 때문)
   ▶️삭제 시,
   좌측 서브트리에서 가장 큰 노드 또는 우측 서브트리에서 가장 작은 노드로 대체

element *search(treePointer tree, int key){
// key 값이 k인 노드에 대한 포인터 반환. 그런 노드가 없는 경우 NULL 반환.
if(!root) return NULL;
if(k == root →data.key) return &(root → data);
if(k < root → data.key)
return search(root → leftChild, k);
else
return search(root → rightChild, k);
}

1. 무방향 그래프
   최대 간선 수: n(n-1)/2

2. 방향 그래프
   최대 간선 수: n(n-1)

3. 강력연결그래프와 강력연결요소(Strongly Conncected Component, SCC)
   모든 정점의 쌍에 대해 방향경로가 존재하면 강력 연결 그래프.
   하나의 강력연결요소(SCC) 안에 있는 어떤 두 정점 u, v를 골라도 SCC 안에서 u -> v로 갈 수 있는 경로가 존재.
   

공부량이 너무 적었네요.. 30문제 실환가
오늘은 정신차려서 많이 좀 하즈아~!