Was gibt es für grundlegende Baum-Datenstrukturen?
-
Hat jemand eine Idee für eine simple Datenstruktur in Baumform? Ich will ein bisschen implementieren üben.
Mir fallen zunächst binärer Suchbaum, Präfixbaum (Trie) und binärer Heap ein. Aber wird der Heap überhaupt jemals als Baum (und nicht als Array) implementiert?
Es gibt zwar sehr viele Spezialfälle wie AVL-Tree (sogar eine Liste der Datenstrukturen auf Wikipedia), aber mich interessieren die grundlegenden Strukturen, nicht Optimierungen und Spezialisierungen davon. Was kennt ihr noch so?
-
Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Ist etwas schwierig einzuschaetzen was du als Spezialisierung/Optimierung ansiehst aber hier ein paar weitere baumartige Strukturen, die mir auf die Schnelle einfallen:
Splay-Tree, Fibonacci-Heap, Union-Find (sehr einfach zum implementieren), B-Baum, Intervall-Baum, Segment-Baum, Range-Tree, Suffix-Baum, Quadranten- und 2d-Baum.Die meisten dieser Baume (ausser der Uion-Find Struktur und vielleicht dem Suffix-Baum) sind ziemlich allerdings schwierig zum implementieren.
-
Och B-Bäume sind auch hübsch einfach zu implementieren.
Und was sind Quadranten-Bäume? Meinst du Quadtrees?
Und was ist ein 2D-Baum?
-
-
Ich habe vor langer Zeit auch mal so ne Frage gestellt:
http://www.c-plusplus.net/forum/234798
-
Super, vielen Dank!