Автоматическая настройка стратегии вращения в деревьях сплайнов

Question

Я должен реализовать структуру дерева сплайнов, используя Java.Имеется класс с именем Node, который имеет:

1. левый, правый дочерний элемент
2. info (int)
3. высота узла

Моя домашняя работа состоит в том, чтобы создать метод "вставки".

Я попробовал некоторые стратегии, но пока это не работает, я пытаюсь получить некоторую помощь не путем получения кода, а с некоторыми идеями, которые могут помочьme.

Итак, моя стратегия сначала состояла в том, чтобы реализовать рекурсивный метод, вставляя информацию точно так же, как двоичное дерево поиска, а затем отображая (используя псевдокод):

    Node splay(Node a, int x):
      if a.height >=3:{
         if (there is a node from "a" with the structure of zigzig or zigzag with x info){
         return a(do the rotation)}
}
      else:{
         return Node(splay(a.left,x),a.info,splay(a.right,x))}

Я не полностьюуверен, что эта идея работает для зигзага и зигзага.

С другой стороны, у меня нет информации о родителе узла, поэтому у меня возникли проблемы с тем, как сделать зигзагообразные повороты, я попыталсяиспользуя a.height == 1, но это будет иметь проблемы

Answer 1

Стратегия, которую вы описываете здесь, называется восходящим расширением и является наиболее распространенным способом увидеть описанное расширение.Вы делаете обычный поиск, чтобы найти нужный вам узел, затем применяете правила из книги воспроизведения (зиг, зигзаг или зигзаг), чтобы перетащить этот узел к корню дерева.

Естьдругая стратегия, которую вы можете использовать для реализации распространения, называемая нисходящим расширением , которая реализует распространение путем изменения формы дерева при перемещении от корня к целевому узлу.Вы можете реализовать операцию splay, разделив дерево на два дерева, называемых левым и правым деревьями, а затем завершите splay, разумно комбинируя эти деревья.Это не требует использования рекурсии и устраняет необходимость в родительских указателях.Вы можете найти подробную информацию о том, как это сделать, в разделе 4 оригинальной статьи Слеатора и Тарьяна о кустарниках .Псевдокод не может быть переведен один на один в Java (например, у них есть явный узел с именем «ноль», который, как они предполагают, вы можете настроить левого и правого потомков), но основная идея не так уж плохаВы проверили их цифры и проработали дела.