"Invalid pointer operation" - Stack

[himitsu]

Stichwort: binär Bäume

Ganz einfach gesagt.

Willst du in einer Liste suchen, dann mußt du diese Liste durchsuchen.
Im schlimmsten Fall mußt du also jeden einzelnen Eintrag prüfen, wenn sich das Gesuchte ganz am Ende versteckt.
Im Durchschnitt muß man also die Hälfte aller Eintrage absuchen, um was zu finden.

Bei einer Hashlist wird ein Hash ('ne Art Quersumme) über die Einträge gebildet. Aus dem Gesuchten bildet man ebenfalls einen Hash.
Nun muß man nur noch den Hash finden und da der Hash kleiner ist, muß man weniger vergleichen, aber muß immernoch jeden einzelnen Eintrag durchsuchen, auch wenn das nun schneller geht.

Der BTree, bzw. der binäre Baum ist eine Art Pfad.
Man ordnert die Einträge dort ein und kann sie dann schneller finden, da man nicht alles durchsuchen muß.
Für den Apfel reicht z.B. schon ein einziger Vergleich.

Code:

      #                      #       #
     / \                     #      / \
    A   B----                #     A   B----
   /   / \    \              #    /   / \    \
  P   A   L    U             #   #   A   L    U
  |   |   |    |             #       |   |    |
  F   U   U    S---          #       #   #    S---
  |   |   |   / \  \         #               / \  \
  E   M   M  #  C   S        #              #  C   S
  |   |   |     |   |        #                 |   |
  L   #   E     H   i        #                 #   #
  |       |     |   |        #
  #       #     #   #        #
                             #
  #Apfel     #Bus            #   #Apfel     #Bus
      #Baum     #Busch       #       #Baum     #Busch
          #Blume    #Bussi   #           #Blume    #Bussi

[edit]
Wäre es nicht toll, wenn die Codeausrichtung irgendwann mal funktionieren würde?

[nahkillo94]

wow! Du machst ganz schön großen Aufwand um mir das zu erklären.

Also das mit der Hashliste klingt machbar. Aber das mit dem Baum nicht. Das suchen im Baum würde dann wahrscheinlich auf Backtracking hinauslaufen.

[jaenicke]

Zitat von nahkillo94:

Aber das mit dem Baum nicht. Das suchen im Baum würde dann wahrscheinlich auf Backtracking hinauslaufen.

Nein, eben genau nicht.
An jeder Kreuzung schaut man welches die richtige ist und kommt so viel schneller zum Ergebnis.