알고리즘 스터디 17일차

목차

1. 이진 트리

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

 

1. 이진 트리

각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리

전 게시글의 트리 유형 2가지 중 일차원 배열 표현 에 해당함 (=>인덱스트리,LCA)

이진 트리의 종류

이진 트리 순차 표

트리의 노드와 배열의 인덱스 사이 상관관계

자식노드의 (인덱스 // 2) 해서 나오는 값이 부모 노드의 인덱스 이다.

위와 같은 인덱스 연산 방식은 세그먼트 트리와 LCA에서 기본이 되는 연산이다.

 

최근에 이진 트리 문제를 풀었는데 위의 밑줄친 연산과 배열 표현을 몰라서 직접 노가다로 했다.

알고보니 간단하고 이진 트리 문제에 대한 자신감이 생긴다. 오늘은 개념만 공부하고 짧게 끝나지만 내일 실전 문제를 푸는것이 기대된다.