Как рассчитать указатели в двоичном дереве с помощью макета Ван Эмда Боаса

Question

Я хотел бы реализовать двоичное дерево, не обращающее внимания на кэш, которое хранится в массиве с использованием макета Ван Эмда Боаса с использованием неявных указателей. Все элементы в дереве являются 32-разрядными целыми числами, и дерево станет довольно большим, поэтому сохранение указателей будет означать как минимум увеличение данных в 3 раза.

Проблема в том, что я не могу придумать ни одного итеративного способа вычисления указателей на левого и правого потомков, учитывая индекс узла (я могу отслеживать любую информацию при обходе дерева). Многие статьи / лекции ссылаются на такие деревья с неявными указателями, но я не видел алгоритма для вычисления указателей. Есть ли эффективный способ сделать это?

Answer 1

У Боба Коупленда очень хорошая реализация деревьев van Emde Boas на GitHub .Он использует неявные указатели и вычисляет указатели, сначала вычисляя указатель в ширину, после которого указатели vEB являются простым условным условием.