Относительно кустарников
Я читаю о деревьях сплайнов в структурах данных и алгоритмах Марка Аллена Весиса
Стратегия расширения похожа на идею вращения, за исключением того, что мы немного более избирательны в отношении того, как выполняются вращения. Мы все еще будем вращаться снизу вверх вдоль пути доступа. Пусть x (не корневой) узел на пути доступа, по которому мы вращаемся. Если родительский элемент x является корнем дерева, мы просто поворачиваем x и корень. Это последний поворот на пути доступа. В противном случае у x есть и родитель (p), и дед (g), и есть два случая плюс симметрии, которые нужно рассмотреть. Первый случай - это зигзагообразный случай. Здесь x - правый дочерний элемент, а p - левый дочерний элемент (или наоборот). Если это так, мы выполняем двойной поворот, точно так же, как двойной поворот AVL. В противном случае мы имеем случай зигзага: x и p либо левые, либо оба правые потомки.
В вышеприведенном тексте, что подразумевает автор под следующим утверждением "Есть два случая плюс симметрии"? даны два случая, но что такое симметры здесь?
Спасибо!
2 ответа
Я думаю, что это просто довольно базовая осевая симметрия:
Пример для случая зигзага, вот 2 симметричных дерева:
g
/ \
p d
/\
c x
/ \
a b
g
/ \
d p
/\
x c
/ \
a b
Например, допустим, что кейс имеет вид "Когда рассматриваемый узел является правым дочерним элементом своего родителя, а родительский - левым дочерним элементом дедушки". В этом случае вы делаете левый поворот, а затем правый поворот. Таким образом, узел подходит к прародителю.
Симметричная часть этого случая - "Когда узел в вопросах является левым потомком своего родителя, а родитель - правым потомком деда". В этом случае вы делаете правое вращение, а затем левое вращение. Таким образом, узел подходит к прародителю.
заменив левую на правую и правую на левую, вы получите симметричный регистр.
В Splay Tree есть только 3 случая вращения. Перечислите это здесь. Вы можете увидеть разницу во время выполнения поиска с и без отображения.