태그: 트리
2편
-
트리 자료구조: 이진 트리, 이진 탐색 트리(BST), 전위·중위·후위 순회
루트·자식·높이 같은 트리 용어부터 전위·중위·후위·레벨 순회, 이진 탐색 트리의 삽입과 검색까지 Python으로 구현하고, 트리 높이, 대칭 트리, 최소 공통 조상(LCA) 문제를 재귀로 푸는 방법을 보여 줍니다.
-
구간 쿼리와 누적합을 위한 트리: 세그먼트 트리, 펜윅 트리, 트라이 구현
구간 합 쿼리가 O(n)이라 느릴 때 쓰는 세그먼트 트리(구간 합·RMQ), 누적합 갱신에 강한 펜윅 트리, 자동완성용 트라이를 C++로 구현합니다. 펜윅과 세그먼트 트리를 언제 골라야 하는지도 비교합니다.