Как я могу устранить пробелы в порядке бинарного поиска в ширину?

Question

Дерево бинарного поиска без пропусков - это самобалансирующееся дерево бинарного поиска со свойством без пропусков .Свойство без пробелов указывает, что в упорядочении дерева по ширине нет пробелов.Разрыв в порядке упорядочения по ширине лучше всего определить с помощью диаграммы.На изображении ниже области, выделенные красными пунктирными кружками, считаются пробелами в порядке упорядочения по ширине:

Если бы это дерево было реструктурировано для устранения пробелов, оно выглядело бы каккак это:

Если бы число 7 было добавлено в это реструктурированное дерево без повторной балансировки, оно выглядело бы так:

Опять же, после удаления пробелов:

Существует ли алгоритм log (n) для обеспечения свойства без пробелов после вставок иудаления в деревья произвольных размеров?

Answer 1

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

Нет.

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

           4
          / \
         2   6
        /|   |\
       1 3   5 7

Чтобы вставить 8, вам нужно получить следующее:

           5
          / \
         3   7
        /|   |\
       2 4   6 8
      /
     1

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

Аналогично, чтобы удалить 1, вам понадобится следующее:

           5
          / \
         3   7
        /|   |
       2 4   6

что, та же проблема.