Panda Noir

JavaScript の限界を究めるブログです。

平衡二分探索木の作り方を思いつきました

平衡二分探索木の作り方を思いつきました。速度とかは考えていません。

追記:このやり方は思いっきり間違えています。作れることは作れます。でもやっていることは結局二分探索です。詳しくは謝罪をご覧ください

作り方

まず、ソート済みの配列を用意します。次にその配列を真ん中を根にしてその左右を枝にします。あとはそれを繰り返します。これで偏りがいっさいない平衡二分探索木ができます。

要素の挿入は…考えたのはソート済みの配列にそれをいれて、ソートしてまた木を組み直すです。これ絶対に遅いですよね。ここは要再考です。要素の削除は同様に配列から消して木を組み直しです。

利点・問題点

利点は完璧に偏りがない点です。問題点は挿入と削除が遅いという点です。そのため、挿入と削除をしなければ多分最速の二分探索木となります。

終わりに

挿入と削除は必要になったら考えます。だれか早いの考えたら教えてください。用途によって使い分けてください。