Как производится экспоненциальный поиск?Экспоненциальные поисковые деревья
Согласно http://en.wikipedia.org/wiki/Exponential_tree, «Экспоненциальный дерево практически идентичен бинарного дерева поиска, за исключением, что размерность дерева не то же самое на всех уровнях. В обычном двоичном дереве поиска, каждый узел имеет размерность (d) 1 и имеет 2d-детей. В экспоненциальном дереве размерность равна глубине узла, причем корневой узел имеет ad = 1. Таким образом, второй уровень может содержать два узла, третий может содержать восемь узлов , четвертый 64 узла и т. д. ".
Но как бы я мог представить это в списке, массиве и т. Д.? Обычные BBST - это способ сказать (или, по крайней мере, похожий): захватить отсортированный массив и начать поиск с его середины (корень BBST) и спуститься вниз, сравнив ключ запроса с текущим дочерним. Это либо больше, либо меньше.
Тайна - каково сравнение за экспоненциальным деревом поиска при поиске ключа запроса? Что можно хранить в таком дереве? Какой-то ум взрывающий мысли - как он уравновешен? Если у кого-то есть простой источник литературы, это было бы здорово!
Огромное спасибо!
Спасибо, @Bogdan, эта статья заставит меня идти. с «как бы я на самом деле представлял это в списке, массиве и т. Д.», Просто случайно путал двоичную кучу с bst) –
Теперь этот URL-адрес является неработающей ссылкой. –