Вставка Splay Tree

Question

Пройдя несколько упражнений, чтобы отточить свои навыки работы с бинарным деревом, я решил реализовать дерево сплайнов, как описано в Википедия: Дерево сплайнов .

Одна вещь, которую я не получаю, это часть о вставке.

Там написано:

Сначала мы ищем x в дереве сплайнов. Если x еще не существует, мы не найдем его, но его родительский узел y. Во-вторых, мы выполняем операцию воспроизведения для y, которая переместит y к корню дерева splay. В-третьих, мы вставляем новый узел x как root соответствующим образом. Таким образом, у или левый или правый потомок нового корня х.

У меня такой вопрос: приведенный выше текст кажется слишком кратким по сравнению с другими примерами в статье. Почему это так? Кажется, здесь есть некоторые ошибки. Например, после разворачивания узла y до корня я не могу просто слепо заменить корень на x и прикрепить y к x как к левому или правому дочернему элементу.

Предположим, что значение еще не существует в дереве.

У меня есть это дерево:

           10
          /  \
         5    15
        / \    \
       1   6    20

и я хочу вставить 8. В приведенном выше описании я найду 6-узел, а в обычном двоичном дереве 8 будет добавлено как правый дочерний элемент 6-узла, однако здесь я сначала чтобы развернуть 6-узел до корня:

            6
           / \
          5   10
         /     \
        1       15
                 \
                  20

тогда любой из этих двух явно ошибочен:

          8                                  8
           \                                /
            6                              6
           / \                            / \
          5   10                         5   10
         /     \                        /     \
        1       15                     1       15
                 \                              \
                  20                             20

    6 is not greater than 8          10 is not less than 8

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

1. узел, который я разместил в корне, меньше нового корня (6 <8) </li>
2. самый правый дочерний элемент узла, который я вывел на корень, также меньше, чем новый корень (20 8)

Однако, если бы я разделил развернутый мной узел, взяв правильного дочернего элемента и добавив его в качестве правого дочернего элемента нового узла, я получил бы следующее:

                        8
                       / \
                      6   10
                     /     \
                    5       15
                   /         \
                  1           20

Но всегда ли это простое изменение даст мне правильное дерево? Мне трудно придумать пример, но может ли это привести к следующему:

• Новое значение, которое я хочу добавить, выше, чем временный корень (узел, который я развернул в корне), но также выше, чем самый левый потомок правого потомка временного корня?

* * Т.е. 1 042. дерево, которое в принципе будет выглядеть так после растопки, но прежде чем заменить корень?

                        10
                       /  \
                      5    15
                          /  \
                        11    20

и я хочу добавить 13, что сделало бы новое дерево таким:

                        13
                       /  \
                     10    15
                     /    /  \
                    5   11    20  <-- 11, on the wrong side of 13

или это может никогда не случиться?

Мой второй вопрос таков: не было бы намного проще просто переписать операцию следующим образом:

Сначала мы ищем x в дереве сплайнов. Если x еще не существует, мы не найдем его, но его родительский узел y. Затем мы добавляем новый узел как левый или правый дочерний узел родительского узла. В-третьих, мы выполняем операцию splay над добавленным узлом , который переместит новое значение в корень дерева сплайс.

выделите мое, чтобы показать, что я изменил.

Answer 1

Я не понимаю, как может возникнуть проблема, которую вы описываете. Если вы хотите вставить 13 в это дерево, вы сначала должны найти, где оно будет:

                    10
                   /  \
                  5    15
                      /  \
                    11    20

С 10 вы идете направо, с 15 вы идете налево, с 11 вы идете направо ... и тогда у вас больше нет элементов. Если бы в дереве было 13, мы бы нашли его правым потомком 11. Итак, согласно правилу, мы выполняем операцию на 11, которая переместит 11 к корню дерева:

                    11
                   /  \
                  10   15
                 /       \
                5         20

Затем мы добавляем 13 в качестве нового корня, с 11 в качестве левого потомка:

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

Теперь нет проблем.

Сначала мы ищем x в дереве сплайнов. Если x еще не существует, мы не найдем его, но его родительский узел y. Затем мы добавляем новый узел как левый или правый дочерний узел родительского узла. В-третьих, мы выполняем операцию воспроизведения на добавленном узле, которая переместит новое значение в корень дерева отображения.

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

Answer 2

новый узел будет добавлен в дерево, как обычное двоичное дерево поиска. Тогда новый узел будет развернут, чтобы быть корнем или первым уровнем от корня. Кроме того, когда мы вставляем новый узел, нам нужно найти место для его размещения, поэтому мы делаем поиск. И все операции, включая поиск в дереве сплайнов, запускают операцию сплайнов. Может быть поэтому статья в Википедии описывает это так. Я просто вставляю новый узел и раскручиваю его. В любом случае дерево становится лучше сбалансированным, чем было. отлично работает здесь

Answer 3

«Splay Tree» сразу же заставил меня вспомнить статью в CUJ, которую я читал некоторое время назад, вы можете найти кое-что там: Реализация Splay Tree в C ++ .

В-третьих, мы вставляем новый узел x как root соответствующим образом. Таким образом, у или левый или правый потомок нового корня х.

Да, но у этого нового корня x должно быть 2 ребенка, поэтому это предложение может показаться странным.