코딩 테스트 합격자 되기 스터디 4주차 - 트리

https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

 

• 트리 개념
• 이진트리 표현
• 이진트리 순회
• 이진탐색트리

트리의 개념

• 노드와 간선으로 이루어진 계층적 자료 구조(부모-자식 관계 존재)
• 순환 허용 X
• 코테에서는 이진트리(자식 노드가 최대 2개인 트리)만 알면 됨

이진 트리 표현

배열

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

인접 리스트

• 각 리스트의 인덱스는 부모 노드
• 자식 노드는 부모 노드에 해당되는 인덱스에 추가
• 특징
  • 배열보다 공간 효율 좋음
  • 자식 노트 찾는 데 오래 걸릴 수 있음(순차 탐색 필요, 이진 트리는 자식이 2개이므로 큰 단점 아님)

이진 트리 순회

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

전위 순회

• 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 방문
• 루트 노드부터 시작

전위 순회 실 예시

트리 복사

→ 루트 노드부터 트리 노드를 순차적으로 복사 가능

중위 순회

• 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 방문
• 루트 노드부터 시작

중위 순회 실 예시

이진탐색트리의 원소를 정렬된 상태로 순회(왼쪽은 부모보다 작다 / 오른쪽은 크다)

후위 순회

• 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순으로 방문
• 루트 노드부터 시작

후위 순회 실 예시

폴더 삭제하기 → 제일 깊숙이 들어있는 폴더부터 삭제해야 함.

이진 탐색 트리의 개념

• 탐색을 효율적으로 하기 위해 만든 이진트리
• 왼쪽 자식 노드는 부모 노드보다 작은 값
• 오른쪽 자식 노드는 부모 노드보다 큰 값

이진 탐색 트리를 활용한 탐색의 효율

보통의 경우(균형 잘 잡힌 경우) O(logN)에 가깝지만 최악의 경우(degenerate tree) O(N)이 최종 연산 횟수가 됨.(트리의 높이가 연산 횟수)

이진 탐색 트리 특성

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

  트리의 개념

  • 노드와 간선으로 이루어진 계층적 자료 구조(부모-자식 관계 존재)
  • 순환 허용 X
  • 코테에서는 이진트리(자식 노드가 최대 2개인 트리)만 알면 됨
  
  
  • 루트 노드 인덱스는 1
  • 왼쪽 자식 노드는 부모 노드 인덱스 * 2
  • 오른쪽 자식 노드는 부모 노드 인덱스 * 2 + 1
  인접 리스트
  • 각 리스트의 인덱스는 부모 노드
  • 자식 노드는 부모 노드에 해당되는 인덱스에 추가
  • 특징
    • 배열보다 공간 효율 좋음
    • 자식 노트 찾는 데 오래 걸릴 수 있음(순차 탐색 필요, 이진 트리는 자식이 2개이므로 큰 단점 아님)

  이진 트리 순회

  • 트리 노드를 모두 방문하는 방법
  • 현재 노드를 언제 방문하는 지에 따라 전위, 중위, 후위 순회로 분류.
  전위 순회
  • 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 방문
  • 루트 노드부터 시작
  전위 순회 실 예시→ 루트 노드부터 트리 노드를 순차적으로 복사 가능
  • 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 방문
  • 루트 노드부터 시작
  중위 순회 실 예시후위 순회
  • 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순으로 방문
  • 루트 노드부터 시작
  후위 순회 실 예시

  이진 탐색 트리의 개념

  • 탐색을 효율적으로 하기 위해 만든 이진트리
  • 왼쪽 자식 노드는 부모 노드보다 작은 값
  • 오른쪽 자식 노드는 부모 노드보다 큰 값
  이진 탐색 트리 특성
  • 최대 탐색 횟수는 트리의 높이와 같다.(최악의 경우 O(N)이지만 균형 유지 시 O(logN)
  • 삽입과 동시에 정렬.
  • map, set의 내부는 균형이진트리로 되어 있다.(키값 기준 정렬O)
  • unordered_가 붙은 STL은 해시임(키값 기준 정렬X)
• 보통의 경우(균형 잘 잡힌 경우) O(logN)에 가깝지만 최악의 경우(degenerate tree) O(N)이 최종 연산 횟수가 됨.(트리의 높이가 연산 횟수)
• 이진 탐색 트리를 활용한 탐색의 효율
• 폴더 삭제하기 → 제일 깊숙이 들어있는 폴더부터 삭제해야 함.
• 이진탐색트리의 원소를 정렬된 상태로 순회(왼쪽은 부모보다 작다 / 오른쪽은 크다)
• 중위 순회
• 트리 복사
• 배열
• 이진 트리 표현