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?