木の回転
木の回転によって平衡をとることができる。そのような平衡をとる技法を採用している木としてAVL木がある。回転によって平衡がとれるのは、回転後に回転方向の部分木の高さ(深さ)が1大きくなり、反対方向の部分木の高さが1小さくなるためである。これにより、全体が平衡となるよう高さを調整できる。
同じノード数の2つの2分木があるとき、回転距離 (rotation distance) とは、一方からもう一方へと変形するのにかかる回転の回数である。この距離に着目すると、nノードの2分木の集合は一種の距離空間を形成する。この距離は対称的で常に正であり、三角不等式が成り立つ。
回転距離を求める多項式時間のアルゴリズムが存在するかどうかは分かっていない。しかし、ダニエル・スレイター、ロバート・タージャン、ウィリアム・サーストンの3人は、任意の2つのnノードの木(n ≥ 11 の場合)の回転距離が最大で 2n − 6 であり、この距離の木の組合せが無数に存在することを示した。