파이썬 알고리즘 인터뷰 트리 간단 정리

트리

• 트리 계층형 트리 구조를 시뮬레이션 하는 추상 자료형 루트 값과 부모-자식 관계의 서브트리로 구성되며 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조(자식도 트리, 그 자식도 트리) 순회에는 재귀가 자연스러움
  • 트리의 각 명칭
    • 루트 시작하는 노드 반드시 트리는 루트로부터 시작해야 함
    • 자식 노드의 노드
    • 간선 부모 트리와 자식 트리를 잇는 선
    • 차수 자식 노드의 개수
    • 크기 자신을 포함한 모든 자식 노드의 개수
    • 리프 루트에서 가장 먼 노드
    • 높이 현재 위치에서 리프 까지의 거리
    • 깊이 루트에서 현재 노드까지의 거리
    • 서브트리 하나의 트리를 구성하는 각각의 작은 트리
    • 레벨 루트인 0 부터 시작하며 자식 노드 한 층마다 내려갈 수록 증가함
  • 그래프 vs 트리 트리는 순환 구조를 갖지 않는 그래프 트리는 그래프의 범주에 포함됨 트리는 양방향 트리는 하나의 부모를 가지며 루트 또한 하나여야 함
  • 이진 트리 각 노드의 차수가 2 이하일 때 단순해서 알고리즘 구현하기 쉬움
    • 이진 트리 유형
      • 정 이진 트리 모든 노드가 0개 또는 2개의 자식 노드를 가짐
      • 완전 이진 트리 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워짐
      • 포화 이진 트리 모든 노드가 2개의 자식 노드를 갖고 있으며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는 트리
    • 이진 탐색 트리 노드의 왼쪽/오른쪽 서브 트리에는 그 노드의 값보다 작은/큰 값들로 지닌 노드들로 이뤄져 있는 이진 트리 시간 복잡도가 O(log n) 균형이 깨지면 탐색 시 O(n) 에 근접한 시간 소요될 수 있음
      • 자가 균형 이진 탐색 트리 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리 AVL 트리, 레드-블랙 트리 등이 있으며 레드-블랙 트리는 높은 효율성으로 인해 실무에서도 매우 빈번하게 쓰임
  • 직렬화 논리적인 구조인 이진 트리를 파일이나 디스크에 저장하기 위해 물리적인 형태로 바꿔주는 것 배열로 표현하기 좋음
    • 역직렬화 배열을 이진 트리로 바꾸는 것
  • 높이 균형 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것 높이 균형이 맞아서 효율적으로 트리 구성할 수 있으며 탐색 또한 훨씬 더 효율적으로 처리 가능
  • 트리 순회 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정 DFS 나 BFS 로 탐색 L 은 현재 노드의 왼쪽 서브트리, R 은 현재 노드의 오른쪽 서브트리, N 은 현재 노드 자신을 의미
    • 전위 순회(NLR) 현재 노드를 순회한 다음 왼쪽, 오른쪽 서브트리 순회
    • 중위 순회(LNR) 왼쪽 서브트리를 순회한 다음 현재 노드, 오른쪽 서브트리 순회
    • 후위 순회(LRN) 왼쪽, 오른쪽 서브트리 순회한 후 현재 노드 순회
• 중첩 함수에서 클래스 변수 사용 중첩 함수에서 부모 함수 변수 재할당이 불가능하기 때문에 사용.