第3回PFDS(Purely Functional Data Structures)読書会で exercise 3.9 のときに紹介された論文「Constructing Red-Black Trees」（この名前でググるとPDF版が見つかる。Postscript版はこちら）に載っている関数 bottom-up の計算量が O(n) であることを確認…