Как хранить неполное бинарное дерево выражений в массиве?

Question

[nickware96]

Как хранить неполное бинарное дерево выражений в массиве? Если хранить так же, как и полное, то появляются пропуски (неиспользуемые ячейки) в массиве. В таком случае ещё нужно будет как-то помечать эти ячейки, что они не используются. Что подскажете? Речь идёт относительно C++.

Answer 1

[Юрий Ярош]

Для хранения транзакций используются вспомогательные структуры, типа lsm-tree.
Советую ещё глянуть как обстоят дела с cache oblivious b-tree.

Comments

[nickware96]

Спасибо, но что-то Вы как-то далеко зашли. Я не упомянул: речь идёт про C++.

[Юрий Ярош]

От языка ничего не зависит, эта структура используется для хранения почти во всех более-менее популярных решениях, начиная от sqlite и leveldb заканчивая всякими mongo и cassandra.

[nickware96]

Юрий Ярош: я понимаю, но такой ответ на первом курсе преподаватель не поймёт. Тут элементарно - есть одномерный статический массив, храним бинарное дерево выражений, и собственно вопрос в сабже.

[Юрий Ярош]

Можно использовать любую вспомогательную структуру.