Rust で平衡二分木を書くのは何となく難しいイメージがありました。 unsafe を使わずに実装できるものなのか気になったので、試しに実装してみました。 結論から言うと、unsafe を使わなくても平衡二分木は実装できました。また、unsafe だけでなく、Rc や RefCell も使っていません。 ただし NLL がないとコンパイルが通りませんでした。NLL は神機能ですね。 Splay 木 今回実装した平衡二分木は Splay 木というものです。 Splay 木は、search や insert などの典型的な操作を償却 時間で実行できます。 また、Splay 木は最後にアクセスしたノードを木のルートに持ってくる性質があるため、アクセスに局所性がある場合によい性能が出るそうです。 平衡二分木といえば何と言っても赤黒木ですが、赤黒木は実装が大変すぎるので今回は却下しました。 アルゴリ
![NLL のおかげで Rust で平衡二分木を実装できた - @nojima's blog](https://cdn-ak-scissors.b.st-hatena.com/image/square/7725f9d71f8ba2c2f4652b4aa4211478bfb0a2fb/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fn%2Fnojima718%2F20181120%2F20181120012345.png)