Search Trees (1)에서 BST와 AVL Tree를 다뤘다. AVL은 "양쪽 자식의 height 차이는 최대 1"이라는 규칙으로 height를 O(log n)으로 강제했지만, delete 시 여러 번의 restructuring이 필요할 수 있다(local fix)는 한계가 있었다. 이번 글에서는 "균형을 유지하는 또 다른 방식들"을 본다:Multi-way Search Tree / (2,4) Tree — 노드 하나에 여러 key를 담아서 height를 줄인다 → Splay Tree — 균형 정보 없이, "자주 쓰는 노드를 위로" 옮기는 것만으로 amortized O(log n) → Red-Black Tree — (2,4) tree를 binary tree로 인코딩해서, AVL과 (2,4)의 단점(여..