[코딩 테스트 합격자 되기] 트리
본문 바로가기

Coding Test

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

[인프런] 코딩 테스트 합격자 되기 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