Декартово дерево: Часть 3. Декартово дерево по неявному ключу

Когда я делал такую штуку для оптимизированной замены TCollection и TList в Delphi, в той литературе, которая мне попадалась на тему, это называлось order statistic tree, без какой-либо привязки к декартовому дереву. Я плясал от дерева отрезков, ведь по-любому же дерево отрезков можно припахать для индексации, и так вышел на то, что могут и припахивают. Моё дерево было АВЛ, а подошло бы и красно-чёрное.

в западной литературе, статьях и Интернете ни одного упоминания о декартовом дереве по неявному ключу мне найти не удалось

Раздобыв Кнута и первую редакцию Кормена, я обнаружил, что там всё это время было упоминание о такой возможности. Кстати, Кнут справедливо упоминает о том, что, раз уж мы в каждом узле храним вес, а неплохо бы и сбалансированное дерево взять WBT, чтоб одним и тем же параметром и балансировалось, и индексировалось. В функциональных ЯП оно почему-то популярно, какой Хаскелль ни возьми, а в императивных скорее КЧ или АВЛ будет.

Никогда и нигде я на этом пути не встретил термина implicit treap.Сегодня я искал про верёвки, и так через NEERC вышел на этот термин. На английской Вики связал термины, а у кого есть доступ, предлагаю в NEERC тоже связать.

Вообще, это так круто, что я бы учебный план составлял так, чтобы продвинутые студенты обязательно написали такой список. А, что касается неявных ключей, то я такими ключами называю нечто более неявное. Это особенность карты, у которой сравнение не функция от ключа и ключа, а от чего-то и чего-то, что не ключ в чистом виде. У меня деревья были интрузивные, то есть, живущие внутри объемлющих объектов, так что весь этот объект и передавался в сравнение, а дальше сами разбирайтесь, как это сравнить. Концептуально это аналогично тому, чтобы ключ в чистом виде-таки посчитать для каждого элемента, но это будет устаревать между обращениями к карте, и не для всех узлов это надо вычислять, а только для логарифма узлов по пути вниз по дереву. Кроме того, даже введение функции вычисления явного ключа для элемента, и потом сравнение явных ключей несколько повредило бы производительности. Имеет смысл не вычислять его полностью, если не надо, и именно так и написать сравнитель.

Дело в том, что в TList можно писать одинаковые указатели, и сам TList не интрузивен, так что интрузия производится в TListSlot, невидимый извне. И в этот слот вгрызание производится дважды: один раз для обычного индекса, второй раз для ускорения IndexOf. Чтобы IndexOf мог работать, он должен для выбранного значения возвращать самый первый индекс среди одинаковых значений, а на случай, если вдруг его удалят, он должен оптимально узнавать следующий такой же. Так что IndexOf должен знать вообще все одинаковые указатели, и в том порядке, как они в списке. Для IndexOf строится карта с составным ключом (значение, индекс в списке). Здесь индекс в списке может гулять, но предполагается, что если в TList вставляют и удаляют какие-то другие значения, то все остальные значения остаются друг относительно друга в том же порядке, так что на конкретный вызов метода TList индексы определены и их можно сравнивать, но между вызовами устаревают, но порядок сохраняется. Так вот, если значения отличаются, а это почти 100% так, то и не надо вычислять индекс в списке, тратя O(log n) времени и превращая общую стоимость в квадрат логарифма.

Можно было вместо составного ключа сделать карту карт. Для оптимального XPath так и было сделано. То есть, если есть <A/><B/><A/><B/><C/>, то для поиска B[2] честно строится карта всех B, упорядоченных по их индексам в объемлющем теге, и среди них ищется второй, который в общем списке окажется четвёртый, а четыре больше двух, где находится B[1]. Учитывая, что в TList почти наверняка все элементы разные, вот прямо очень не хотелось два слоя, так что сделал карту в один слой, но с составным ключом, и по возможности во всей полноте вычислять этот ключ не надо. Чтобы искать по карте, можно сделать поиск (значение, -1), и ничего не найдётся, но относительно этого ничего можно посмотреть значение в более правом элементе, и если совпадает, то это то, что надо.