С++, расширяющий структуру данных STL

Мое требование состоит в том, чтобы иметь возможность быстро получить минимальное и максимальное значение в дереве. (Обратите внимание, не ключ минимум/максимум, а минимум/максимум спутниковых данных).

Дерево будет основано на строках в качестве ключей, и каждый узел будет хранить с ним целое число. Это целое число должно меняться и постоянно обновляться. Ключи остаются фиксированными

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

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

Что было бы лучшим подходом, чтобы избежать переписывания реализации STL красного/черного дерева.


c++ data-structures tree red-black-tree stl
person Leon    schedule 19.01.2014    source источник
comment
boost мультииндексный контейнер?   -  person Yakk - Adam Nevraumont    schedule 19.01.2014
comment
@Yakk спасибо за предложение. Выполнит эту работу, но, похоже, это будет немного излишним, так как мне не нужно сортировать вторичный индекс, мне просто нужно отслеживать мин/макс вроде кучи мин/макс   -  person Leon    schedule 19.01.2014
comment
Вы не всегда можете получить то, что хотите. Вы не всегда можете получить то, что хотите. Но если вы попробуете несколько раз, вы получите то, что вам нужно. В качестве альтернативы вы можете написать свой собственный мультииндекс для увеличения повышения, добавив тот, который просто поддерживает элемент min/max (приоритетная очередь?), но это много работы, и вас это действительно волнует?   -  person Yakk - Adam Nevraumont    schedule 19.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вы не можете использовать контейнер STL (например, set, который технически мне даже не нужен BST, насколько мне известно), поскольку он не предоставляет вам доступа к базовой структуре.

Ваши варианты:

  • Как вы уже упоминали, написание собственного BST.

  • Просто используя вторичный BST (или кучу), который упорядочен по вашему целочисленному значению.

  • Используя multi_index_container Boost.

person Bernhard Barker    schedule 19.01.2014