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

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

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

16
задан Lukáš Lalinský 5 February 2011 в 18:21
поделиться