Mapの実装

Mapのリファレンスには "The implementation uses balanced binary trees." とある．ソースのbalを読む限り，どうもAVL木の変種のようだ．普通のAVL木と違って，左右の部分木の高さの差が2まではOKとしている．なお部分木の高さを内部ノード毎にキャッシュすることで少々の効率化を図っているようだ．

• http://camlcvs.inria.fr/cgi-bin/cvsweb/ocaml/stdlib/map.ml?rev=HEAD

ちなみに私がAVL木を初めて習ったのは教養の計プロ（計算機プログラミング）IIである：

• http://lecture.ecc.u-tokyo.ac.jp/~yamaguch/cp2-10/what-is-search.html 検索木

追記： 今は「プログラム構成論」とかいう名前になったらしい．中身はほぼ一緒のようだが．