実装したいので、Splay ツリーを研究しています。現在、Red-Black ツリー、AVL ツリー、Skip リスト、およびその他の単純なデータ構造について、「独学」の経験があります。最初のスプレイ ツリーを実装したいのですが、可能であれば再帰的な実装が必要です (再帰が大好きです)。
ただし、考えられるすべてのケース (ジグザグ、ジグジグ、ザー) を観察するには、ツリーの 2 レベル下を見る必要があり、別のフィールドがないとターゲットをマークする方法がないため、難しいと思います。赤黒の木のように、別のフィールドを使用して、訪問したノードをマークし、ターゲット ノードを拡大する必要がありますか?
再帰アルゴリズムを使用するのは簡単で、かなりきれいに見えるかもしれません。マーキングは不要です。スプレイ操作 (検索、挿入、および削除に使用される) は、ターゲット ノードをツリーの一番上に移動することに注意してください。つまり、ターゲット ノードが一番上にある (展開された) ツリーを返します。
本質的には、与えられたノードから、次の 2 つの移動 (左から左、右から右、またはその他) を決定する必要があります。同じ方向に 2 回移動すると、回転が発生します。
Chris Okasaki のPurely Functional Data Structuresには関数型言語の優れた実装があり、これは現存する最高の短い CS テキストの 1 つです。
ウィキペディアで、スプレー ツリーに関する非常に優れた記事を見つけることができます。再帰は簡単に手に負えなくなる可能性があるため、再帰を愛すべきではありません。反復性を使用することをお勧めします。