지난 글에서 Map and Hash 단원을 정리하면서 마지막에 남겨둔 문제가 하나 있었다: Sorted Map(sorted search table)은 binary search로 탐색이 O(log n)이지만, insert/delete는 배열을 shift해야 해서 여전히 O(n)이다. 이 단원(Search Tree)은 이 문제를 해결하는 게 목표다. 큰 흐름은:BST(Binary Search Tree) — 트리 구조로 정렬된 데이터를 표현하면 insert/delete에서 shifting이 필요 없다. 하지만 트리가 한쪽으로 치우치면 height가 O(n)이 될 수 있다 → AVL Tree — "양쪽 자식의 height 차이는 최대 1"이라는 규칙을 추가해서, height를 O(log n)으로 강제한다. ..