2-3 フィンガーツリー
ここでは#分割の一般化で示した分割演算を使った応用例を示す。
2-3フィンガーツリーは分岐数が2または3である木構造に対して「指(finger)」と呼ばれる構造を導入して作られる。 通常の平衡木では葉に置いた要素にアクセスする際には根から参照を辿る必要があり、要素数に対して対数時間の計算量が必要となる。しかし多くの場合、頻繁にアクセスする要素は特定の場所やその周辺に偏っている。例えば両端キューの場合、ほとんどの演算は両端やその周辺に対する演算である。そのため毎回根から参照を辿るのは効率が悪い。そこで参照を辿る開始点を変更し、必要に応じてポインタを反転させておき頻繁にアクセスする部分に素早くアクセスできるようにする。この構造を指と言う。以下は完全二分木の両端に対して指を導入した例である(2-3フィンガーツリーではない)。
まず参照を辿る開始点を両端にする。親からそのノードへの参照を反転させる。そして親から親の親への参照も再帰的に反転させていく。すると両端に近い部分へは素早くアクセスできるようになる。完全二分木の両端に指を導入したものは最初の部分を除いて、2つの完全二分木を要素として持つリストとしても見られる。各完全二分木のサイズは2倍ずつに増えていく。
2-3フィンガーツリーは分岐数が2または3である木構造の両端に指を追加したものであり、分岐数が2または3である木のペアを要素として持つリストとしても見られる。