c - splay ツリーをトラバースすると、ルートはどれでしょうか?

Question

スプレイ ツリーを使用している場合、最後にアクセスした要素がルート ノードに到達するのではないかと疑っていました。私のツリーが

                     5
                    / \
                   3   7
                  / \ / \
                 2  4 6  8

順序通りのトラバーサルを実行すると、出力は次のようになります

     2 3 4 5 6 7 8 

したがって、ここで最後にアクセスされた要素は です8。疑問があるので、8が最後にアクセスされたノードになるので、ルートノードとして移動したい8ですか?

Answer 1

あなたの論理は正しいです。ただし、スプレイの操作は、トラバーサル中ではなく、挿入および検索中にのみ行われます。ノードを挿入または検索すると、その後すぐにアクセスできるように、ノードが最上位に移動されます (ルート ノードとして作成されます)。