Когда я пересекаю дерево сплайнов, то какой из них является корневым?
У меня были сомнения, когда мы используем Splay Tree, последний доступ к элементу придет к корневому узлу. рассмотреть мое дерево
5
/ \
3 7
/ \ / \
2 4 6 8
когда я выполняю обход Inorder, вывод будет
2 3 4 5 6 7 8
так что здесь последний доступный элемент 8В этом у меня есть сомнения, поэтому 8 будет последним доступным узлом, поэтому мы хотим переместить 8 как корневой узел или нет?
2 ответа
Ваша логика верна. Но операция расширения выполняется только во время вставки и поиска, а не во время обхода. Когда вы вставляете или ищите узел, он перемещается вверх (сделан как корневой узел), чтобы впоследствии к нему можно было быстро получить доступ.
Вы можете выбрать любой путь. Здесь есть несколько факторов.
Классический алгоритм неупорядоченного обхода бинарных деревьев является рекурсивным, а расширенные деревья могут быть настолько глубокими, насколько у них есть узлы, потому что они не строго сбалансированы. Таким образом, рекурсивный обход расширенного дерева по порядку может легко исчерпать пространство стека — и он может занять столько же памяти, сколько само расширенное дерево!
Если в расширенном дереве есть узлы с родительскими указателями, неупорядоченный обход может быть выполнен без рекурсии и без расширения. Это потому, что вы можете найти предшественника и преемника, следуя левым, правым и родительским указателям.
Также можно эффективно перебирать узлы расширенного дерева в следующем порядке:
- Найдите наименьший элемент и растяните его до корня.
- Найдите его преемника и расправьте его в корень.
- Найдите его преемника и расправьте его в корень. И т. д.
- Продолжайте, пока не останется преемника.
В этом случае, когда все будет сделано, корень будет самым большим элементом.
Неупорядоченный обход растянутых деревьев (или https://doi.org/10.1016/S1571-0661(04)80771-0) описывает, почему этот подход эффективен. Посещать каждый узел расширенного дерева по порядку, расширяясь каждый раз, почти O(n).