Ich mache einen Baum (im Wesentlichen ein Präfix Baum, aber für Zahlen nicht Strings), die aus sortierten Liste von Tupeln von Zahlen ((1,1,2), (1,2,5), (2, 1,0) etc ...), die jeweils einem einzelnen Skalarwert (int oder double am wahrscheinlichsten) zugeordnet sind. Da es nur einmal erstellt und dann mehrmals durchlaufen/durchsucht wird, plane ich, std :: vectors zu verwenden, um die untergeordneten Elemente jedes Knotens zu halten. Um den Baum zu durchsuchen, muss ich einfach std :: lower_bound aufrufen, um eine binäre Suche auf dem _children Vektor jedes Knotens durchzuführen, der std :: -Paare jedes Knotens und ihren jeweiligen Schlüssel enthält. Die untersten Knoten müssen jedoch einen Vektor mit Paaren enthalten, die aus dem letzten Eintrag in jedem Tupel und ihren jeweiligen Werten bestehen und daher von einem anderen Typ als der BranchNode sein müssen. Der Code sieht wie folgt aus:C++: Getrennte Klassen für Zweig- und Blattknoten?
class GenNode
{
};
template<typename key_type,typename value_type>
class BranchNode : GenNode
{
void insert(std::pair< std::vector<key_type> , value_type>);
private:
std::vector< std::pair<key_type,GenNode*> > _children;
};
template<typename key_type,typename value_type>
class LeafNode : GenNode
{
private:
std::vector< std::pair<key_type,value_type> > _children;
};
Allerdings ist dies wirklich hässlich ist, da beide Klassen von der nutzlosen GenNode Klasse erben müssen, damit die Kinder jedes BranchNode entweder andere BranchNodes oder LeafNodes sein kann ... gibt es eine bessere Möglichkeit, dies zu tun?
Ein 'Node' ist ein Blatt, bis ihm Unterknoten hinzugefügt wurden, dann ist es ein Zweig. Habe einfach 'Node'-Objekte. –
Ich möchte das aus Gründen der Effizienz nicht machen; Ich will nicht der Blattknoten leer _children Vektoren haben, die vermutlich noch eine „size = 0“ speichern und mit anderen ähnlichen Elementen –
Es gibt eine Diskussion über die Vorzüge des verschiedenen Baum Implementierungen im Kommentarbereich dieser Blog-Post: http : //math.andrej.com/2009/04/11/on-programming-language-design/ – Heatsink