Опять же, как уже отмечалось, это интересная, но нетривиальная проблема - спасибо! Теперь я знаю, как мне провести эти выходные :-) Я мог бы также рассмотреть идею кучи, но я бы превратил ее в кучу с резьбой. Каждый узел в куче содержит указатель на «индекс» ACL, если хотите.
Предположим, у меня есть только три узла в примере (R (oot), P (не) и N (ode)). Таким образом, ACL, установленный для N, представляет собой ACL (R) + ACL (P) + ACL (N). Предположим, что при создании узла этот узел содержит указатель X, который указывает на индекс узла. Итак, R (X) = ACLIndex (R). Ни один узел сам по себе не содержит свой ACL.
Теперь, для данного узла N, мне все равно придется гоняться от корня в худшем случае, но я просто прыгаю по плоскому индексу, чтобы сделать это, а не прыгаю по всему дереву. Было бы лучше, если бы вы могли утверждать, что для данного узла N существует только один путь к N, или, если существует несколько путей, N хранит другую таблицу обходов так, что для N путь (N) из узел A прослушивается в этой таблице. По сути, вы должны оставить крошки в N, когда к нему присоединяется узел.
Мне интересно, можем ли мы заимствовать понятие из геолокации. Для вашего маленького портативного GPS-приемника невозможно сохранить все возможные маршруты кратчайшего пути из любой точки в любую точку и помнить о времени движения. Он обманывает и разделяет карты на «плитки». Поскольку вы не можете быть на всей карте одновременно, а наоборот, вы ограничены плиткой, в которой находитесь в данный момент, ему нужно только вычислить кратчайшие пути изнутри. та плитка к ее известному существует. Как только вы выходите, он загружает этот тайл и повторяется. По сути, мы используем принцип локальности, чтобы уменьшить масштаб.
Что если бы мы использовали ту же идею? Для данного узла, если вы разделили дерево доступа на «сегменты», вы могли бы предварительно рассчитать затраты или, по крайней мере, обновить их, и тогда стоимость пути от R до N представляет собой просто сумму затрат на сегменты плюс стоимость пути в вашем местном осколке.