Splay tree：スプレイツリーの順番にノードを順方向に調べますか？

Question

これで、私のスプレイツリーの正しいノード順序をチェックするために、インオーダートラバーサルを使用して、これで試験を終わりました。これは有効ですか？

Answer 1

はい、インオーダートラバーサルは、スプレイツリーの要素を昇順でアクセスします。スプレー木in the original articleの定義により

：

スプレー木、（された）二分探索木の自己調整形

ので、スプレー木は普通のですバイナリ検索ツリーを構造単位で使用します。これは、順番に要素をアクセスするために順序通りのトラバーサルに必要なすべてです。それ以外は、スプレイツリーの検索パスに沿った操作は構造を変更しますが、binary search tree invariantsに違反しない方法で行います。