[코딩 테스트 합격자 되기] 트리

[인프런] 코딩 테스트 합격자 되기 C++

강의 링크 : https://www.youtube.com/watch?v=CXiVJgUjL6o&embeds_referring_euri=https%3A%2F%2Fwww.inflearn.com%2F&source_ve_path=MjM4NTE

 

<Tree>

[트리 용어]

• 차수 (degree) : 노드의 자식 수
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수

[이진 트리 표현 - 배열]

• 루트 노드 인덱스 : 1
• 왼쪽 자식 노드 : 부모 노드 인덱스 * 2
• 오른쪽 자식 노드 : 부모 노드 인덱스 * 2 + 1

구현 쉽지만, 빈 공간이 많음 (메모리 공간 낭비)

 

[이진 트리 표현 - 인접 리스트]

• 각 리스트의 인덱스는 부모 노드
• 자식 노드는 부모 노드에 해당되는 인덱스에 추가

공간 활용도가 높음, 자식 노드를 찾는데 오래 걸릴 수 있음 (순차 탐색 필요, 이진 트리는 자식이 2개이므로 크게 단점은 아님)

 

[이진 트리의 순회]

트리의 노드를 모두 방문하는 방법현재 노드를 언제 방문하는지에 따라 전위순회, 중위순회, 후외순회로 분류됨

• 전위 순회 : 부모 -> 왼쪽 자식 -> 오른쪽 자식 노드
  • 1 -> 4 -> 3 -> 2 -> 5 -> 8 -> 7 -> 6
  • 예시) 트리 복사 - 루트노드부터 트리 노드를 순차적으로 (부모부터 차례대로) 복사할 수 있음
• 중위 순회 : 왼쪽 -> 부모 -> 오른쪽
  • 2 -> 3 -> 4 -> 5 -> 1 ->  8 -> 6 -> 7
  • 예시) 이진 탐색 트리의 원소를 정렬된 상태로 순회할 수 있음 (왼쪽은 부모보다 작다 / 오른쪽은 크다)
• 후외 순회 : 왼쪽  -> 오른쪽 -> 부모
  • 2 -> 3 -> 5 -> 4 -> 6 -> 7 -> 8 -> 1
  • 예시) 폴더 삭제 하기 - 제일 깊숙이 들어있는 폴더부터 삭제해야 함

 

[이진 탐색 트리 특성]

• 최대 탐색 횟수는 트리의 높이와 같다 - 최악의 경우 O(N)이지만 균형 유지시 O(logN)
• 삽입과 동시에 정렬을 한다 - 최악의 경우 O(N)이지만 균형 유지시 O(logN)
• In c++,
  • map, set의 내부는 균형 이진 탐색 트리로 되어있음 (키 값 기준 정렬 O)
  • unordered_가 붙은 STL은 해시임 (키 값 기준 정렬 X)

---

풀어볼만한 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42892 https://school.programmers.co.kr/learn/courses/30/lessons/12985