問題タブ [splay-tree]

スプレー ツリー用の C++ テンプレート構造体を作成しようとしていますが、コードをテストしようとすると、非常に奇妙な結果が得られます。

これはテンプレートの私のコードです:

これを使用してテストしています：

要素 2 を挿入し、ルート ノードの値を 2 回出力しました。どういうわけか、2 つのプリントから 2 つの異なる値が得られました ( http://ideone.com/RxZMyAの Ideone では 2 と 10 )。コンピューターでプログラムを実行すると、代わりに 2 と 1875691072 が返されました。どちらの場合も、2 の後に 3 を挿入すると、ルート ノードの左の子は、2 を含むノード オブジェクトである必要があるときに null ポインターでした。

同じものを2回印刷すると2つの異なる値が得られる理由と、splaytree.add()関数を意図したとおりに機能させるためにできることを教えてください。ありがとう！

n 個のキー 1,2,…,n をこの順序で挿入する場合、

(a)。通常の BST (Binary Search Tree) に

(b)。スプレイツリーへ

それぞれのケース (a)、b) の複雑さはどのくらいですか?

どちらの場合も O(log n) ですか? それとも、(a) は O(log n) で、(b) は O(M log n) ですか?