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

Question

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

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

Answer 1

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