2024 - 06 - 25 C++ 코딩테스트 10주완성 D+15

2주차 개념정리 - 2

 

이진트리

---

각각의 자식노드가 2개이하로 구성된 트리를 말하며 이를 다음과 같이 분류합니다.

 

이진 트리의 종류

 

• 정이진 트리 : 자식 노드가 0 또는 2개인 이진 트리를 의미합니다.
• 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다. 
• 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리를 의미합니다.
• 포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리를 의미합니다.
• 균형 이진 트리 : 모든 노드의 왼쪽하위 트리와 오른쪽 하위트리의 차이가 1이하인 트리입니다. map, set를 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나입니다.

 

이진탐색트리(BST, Binary Search Tree)

---

이진트리의 일종으로

 

노드의 오른쪽 하위 트리에는 "노드의 값보다 큰 값" 이 들어있고,

 

노드의 왼쪽 하위 트리에는 "노드의 값보다 작은 값" 이 들어있는 트리를 말합니다.

 

이진 탐색 트리 예시

만약 예시의 이진트리에서 ' 1 ' 이라는 숫자를 탐색하고 싶으면

 

5번부터 시작하여 5 -> 3 -> 2 -> 1 순서로 탐색한다.

 

따라서 4번의 시간복잡도를 가진다.

 

이렇게 이진탐색트리의 시간 복잡도는 기존 노드랑 비교하여 큰수 작은 수로 나뉘어

 

탐색,삽입,삭제,수정을 하기 때문에 모두 O(log N) 입니다.

 

인접 행렬

---

 

인접행렬이란 정점과 간선의 관계를 나타내는 Bool 타입의 정사각형 행렬을 의미합니다.

 

인접 행렬 이미지 예시

예시 이미지의 인접행렬을 코드로 나타내면

 

Bool a[4][4] = {
                         {0, 1, 0, 0},
                         {1, 0, 1, 0},
                         {0, 1, 0, 1},
                         {0, 0, 1, 0}
                         };

 

이 행렬을 이용하여 정점과 간선 관계를 반복문을 이용하여 찾을 수 있다.

bool a[V][V];
for(int i = 0;i < V; i++){
    for(int j = 0; j < V; j++){
        if(a[i][j]){
            //출력하는 로직
            cout << i << "부터 " << j << "까지 경로가 있습니다.\n";
            // 해당 정점으로 부터 탐색하는 로직
            bfs(i);
            dfs(i);
        }
    }
}

 

2차원 Bool형 행열을 선언하였으니, 반복문을 이용하여 찾을 때에도, 중첩 반복문을 써야 찾을 수 있다.