Дерево с повторяющимися записями у листьев

Question

У меня есть данные, хранящиеся в листьях дерева. Доступ к листьям осуществляется с помощью ключа, который является кортежем объектов. Дерево потенциально огромно, и я хотел бы его конденсировать. Например:

 * 
    /\ 
     a b 
    /|\ \ 
    1 2 5 1 
//| |\ |\ 
    x x y x z y z <-- Leaves 
    | | | | | | | 
    1 2 7 1 3 1 1 <-- Values at leaves 

кортежей (*, a, 1, x) и (*, a, 5, x) оба приводят к значению 1 в листьях и так дерево может быть конденсирован:

 * 
    /\ 
     a b 
    /\ \ 
    A 2 1 
    /| /| |\ 
    x z x y y z 
    | | | | | | 
    1 3 2 7 1 1 

, где A представляет собой 1 или 5. Конечно, поиск замедляется тем, что нужно проверить членство в наборе A. Я ищу источник, который описывает эту структуру данных и связанные с ней процедуры.

Я использую C++ в том случае, если кто-то вдохновляется поделиться проблемами с кодом.

Answer 1

Не зная, для чего вы используете дерево, трудно дать рекомендации, но я считаю, что такая древовидная структура никогда не будет действительно полезной на практике, поскольку гораздо проще использовать какой-то сортированный набор или ассоциативная карта, чем эта.

Однако, если у вас уже есть древовидная структура и вы хотите сохранить эффективность точно так, как она есть сейчас, вы можете вместо слияния ветвей заменить все листья указателями на данные. Таким образом, вы можете хранить каждый объект данных один раз и иметь несколько листов, указывающих на один и тот же объект данных. Это также наиболее гибкое решение, потому что вы все равно можете изменить значение любого листа, просто изменив указатель, тогда как в идее слияния филиалов его нельзя отменить, не имея постоянной структуры данных.