Splay tree: просмотр обхода по порядку просматривает узлы в порядке возрастания для splay tree?

Question

Я только что закончил экзамен по этому вопросу, где я использовал обход по порядку, чтобы проверить правильный порядок узлов в одном из моих деревьев сплайнов. Это действительно?

Answer 1

Да, обход по порядку обращается к элементам Splay Tree в возрастающем порядке.

По определению Splay Tree в оригинальной статье:

Splay Tree (является) саморегулирующейся формой бинарного дерева поиска

Таким образом, Splay Tree - это просто обычное двоичное дерево поиска по структуре, которое является всем, что требуется для обхода по порядку для доступа к элементам в возрастающем порядке. Кроме того, операции вдоль пути поиска дерева сплайнов изменяют структуру, но они делают это таким образом, чтобы не нарушать инварианты двоичного дерева поиска.