Использование 2-3 дерева для поддержки списков

Question

Предположим, мы пытаемся поддерживать структуру списка, используя 2-3 дерева, и хотим иметь эффективные операции для создания списка, объединения, разделения и получения значения по индексу.Моя первая попытка сделать это - представить элементы списка как листья в дереве 2-3, и каждый внутренний узел хранит количество листьев слева.Таким образом, если вы хотите искать индекс, то если индекс, который вы ищете, меньше, чем значение на любом внутреннем узле, он будет смотреть влево, а в противном случае - вправо.Если не удается найти лист, то индекс выходит за пределы.

Однако я не уверен, как эффективно поддерживать этот инвариант при объединении списков.Я мог бы привязать древовидное представление L2 к самой правой доступной позиции в дереве для L1, а затем попытаться обновить счетчики, а затем попытаться реализовать некоторый алгоритм вставки, подобный этому для 2-3 деревьев ... но по крайней меремоя интуиция говорит мне, что я не смогу сделать это эффективным (т. е. O (log (n))).

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

Answer 1

(Я собираюсь ответить на красно-черное дерево вместо дерева 2-3, так как его легче рассуждать. Этот ответ требует небольшой адаптации для работы с деревом 2-3)

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

Этот инвариант не нуждается в обновлении при объединении или разбиении двух списков.

Чтобы объединить два списка A и B (то есть B добавляется к A ), просто создайте новую вершину v и сделайте A и B левойи правильные дети соответственно.Обновите число элементов в поддереве с корнем в v , чтобы оно стало суммой количества элементов в A и B .

Twoразделите список на два, просто удалите ребро, идущее к корню списка, который вы хотите вырезать.

(ОБНОВЛЕНИЕ)

Однако в зависимости от размера списков дерево может стать неуравновешенным.После определенного количества «несбалансированных» конкатенаций или разбиений вам придется перебалансировать дерево.Я должен признать, я не совсем уверен, какова временная сложность этого.Я почти уверен, что вы не можете получить амортизированное постоянное время, но вы можете получить амортизированное время O (log n).