回転距離
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 07:14 UTC 版)
同じノード数の2つの2分木があるとき、回転距離 (rotation distance) とは、一方からもう一方へと変形するのにかかる回転の回数である。この距離に着目すると、nノードの2分木の集合は一種の距離空間を形成する。この距離は対称的で常に正であり、三角不等式が成り立つ。 回転距離を求める多項式時間のアルゴリズムが存在するかどうかは分かっていない。しかし、ダニエル・スレイター、ロバート・タージャン、ウィリアム・サーストンの3人は、任意の2つのnノードの木（n ≥ 11 の場合）の回転距離が最大で 2n − 6 であり、この距離の木の組合せが無数に存在することを示した。
※この「回転距離」の解説は、「木の回転」の解説の一部です。
「回転距離」を含む「木の回転」の記事については、「木の回転」の概要を参照ください。
ウィキペディア小見出し辞書の「回転距離」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 回転距離のページへのリンク
