二分探索木とはデータ構造の一つです。
平衡を保った二分探索木は、二分探索を最も効率よく行う事ができます。

しかし、どんな場合でも平衡を保つとは限りません。
最悪なのはキー値の出現順序が１、２、３…となっている場合で、
図のように平衡を保てず、リスト構造と同様な探索効率になってしまいます。

常に平衡を保つ為には、木の回転という操作が必要になります。
ただ、この操作にも当然ながら処理時間が必要で、
タイムクリティカルな局面では、こういった処理すらケチりたくなってきます。
（処理時間そのものより、処理を挟む事による処理時間のばらつきが問題になる）

もし、キー値を自由に割り振る事が可能なら、ランダム値を割り振る事で
木の回転をしなくても、二分探索木は常に平衡を保つようになります。
しかししかしタイムクリティカルな局面では、乱数計算すらケチりたくなってきます。

乱数計算不要で、二分探索木が平衡を保つような数列…。頭をひねったところ、
１、２、３…の、各値のビット列を反転したものを数列にすればよい事に気付きました。

［計算例］
1,2,3…15の各値を8ビット値とみなし、それぞれビット列を反転させます。
すると次のような数列が得られます。

128,64,192,32,160,96,224,16,144,80,208,48,176,112,240

このキー順に二分探索木を構築していくと、図のように常に平衡を保ちつつ成長します。

なお、ビット列の反転は非常に高速なアルゴリズムが知られています。
http://graphics.stanford.edu/~seander/bithacks.html

さて、いくら木の回転が不要といっても、ランダムにノード削除が発生すると
ノード間が寸断されてしまい、ノードの再配置が避けられなくなります。
従ってこの方法で高速化が期待できるのは、スタックのように
データの追加削除がLIFOで行われるケースに限られるでしょう。