목차
이 책으로 공부하는 법
한 장은 파트 둘과 실습이다
읽는 순서
지면의 약속
코드
1. 세그먼트 트리 — 자리를 반씩 나눈 구간마다 접은 값을 적어 두면 고치기와 구간 접기가 함께 노드 몇 개로 끝나는 이유
2. 펜윅 트리 — 칸마다 최하위 1 비트 길이의 구간 합을 겹쳐 두면 고치기와 앞구간 읽기가 함께 칸 몇 개로 끝나는 이유
3. 트라이 — 접두사마다 노드를 하나씩 두면 다섯 연산이 담긴 낱말 수를 보지 않고 받은 문자열의 길이만큼만 내려가는 이유
4. 라딕스 트리 — 갈림 없는 구간을 간선 하나로 접고 라벨을 담긴 낱말의 구간으로 들면 가르고 합치는 일이 수 몇 개로 끝나는 이유
5. 삼분 탐색 트리 — 같은 자리의 문자끼리 이진 탐색 트리로 이어 두면 노드마다 링크 셋만으로 접두사를 찾고 낱말을 사전순으로 꺼내는 이유
6. 최소 힙 — 부모가 자식보다 앞서게만 두어도 맨 앞 원소가 늘 뿌리에 있는 이유
7. 최대 힙 — 합치기가 지나온 노드마다 좌우를 맞바꾸면 긴 오른쪽 길이 왼쪽으로 옮겨 가는 이유
8. 우선순위 큐 — 원소를 부분적으로만 정렬해 두면 넣기와 빼기가 뿌리에서 잎까지 한 줄만 고치는 이유
9. d-진 힙 — 갈래 수를 바꾸면 넣기와 빼기의 비용이 반대로 움직여도 계약이 그 수를 고르지 못하는 이유
10. 단조 스택 — 넣고 빼는 끝이 같으면 넣을 때 적어 둔 최댓값이 빼기 뒤에도 맞다
11. 단조 큐 — 원소마다 한 번만 정리해 두면 앞 끝이 빠져도 최댓값을 다시 찾지 않는다
12. LRU 캐시 — 항목 하나를 표와 쓴 순서 줄이 함께 들면 찾은 자리에서 순서를 고치고 가장 오래 안 쓴 키를 곧바로 빼는 이유
마무리
시리즈 구성
이 책
참조 표기