Вставка расширенного дерева

Question

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

Единственное, чего я не понимаю, это часть о вставке.

Там говорится:

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

Мой вопрос таков:Приведенный выше текст кажется слишком кратким по сравнению с другими примерами в статье, почему?Кажется, здесь остались некоторые ошибки.Например, после расширения узла 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)
2. самый правый дочерний элемент узла, который я расширил до корня, также меньше нового корня (20 8)

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

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

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

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

Т.е.дерево, которое будет выглядеть так после расширения, но до того, как я заменю корень?

                        10
                       /  \
                      5    15
                          /  \
                        11    20

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

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

или этого никогда не произойдет?

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

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

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

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

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

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

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

Answer 3

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