% Dieses Dokument ist in der Zusammenarbeit von angehenden und
% ausgebildeten Informatiklehrkräften entstanden.
% Der Herausgeber dieses Dokuments ist die Fachgruppe Informatische
% Bildung in NRW der Gesellschaft für Informatik.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% https://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% https://matsam.fg-ibn.gi.de
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter https://www.ctan.org/pkg/schule
% zur Verfügung.

\addcontentsline{toc}{chapter}{Einleitung}
{\chapter*{\dunkel{Einleitung}}}
Mit wachsenden Speichergrößen und immer günstiger werdenden Speicherpreisen ist absehbar, dass große Mengen von Daten verwaltet werden müssen. Dass hierfür effiziente Verfahren notwendig sind, ist einleuchtend. Niemand möchte erst lange warten, bis eine angeklickte MP3 auf der Festplatte lokalisiert und in den Speicher geladen wird -- das Informatiksystem muss innerhalb von Sekundenbruchteilen \enquote{wissen}, wo genau die Datei sich befindet, um sie laden zu können.

Ein Verfahren zur Verwaltung von dynamisch wachsenden und sich verändernden Datenbeständen haben Sie bereits kennengelernt: Die lineare Liste. Mit ihrer Hilfe ist es möglich, Daten zu einer bestehenden Liste hinzuzufügen, Elemente daraus zu entfernen und die Liste mittels der linearen Suche elementweise zu durchsuchen.

Wie Sie sich vorstellen können, stößt diese Datenstruktur schnell an ihre Grenzen, wenn es darum gehen soll, \enquote{schnell mal} ein bestimmtes Element zu finden. Darum werden Sie in diesem Leitprogramm eine neue Datenstruktur kennen lernen, die Ihnen neue Möglichkeiten eröffnet. Wir beginnen damit allerdings nicht im oder am Informatiksystem, sondern stellen uns vor ein CD-Regal \ldots\vspace{2cm}
\begin{center}
    \begin{tikzpicture}[y=1cm, x=1cm, scale=0.8, inner sep=0pt, outer sep=0pt]
        \path[fill=grey8,line cap=round,line width=0.1069cm] (3.9688, 3.786) ellipse (3.709cm and 3.786cm);
        \path[draw=black,line cap=round,line width=0.1588cm] (3.9688, 3.9158) circle (3.9688cm);
        \path[fill=white,line cap=round,line width=0.0132cm] (3.6326, 7.238).. controls (4.2489, 7.5563) and (5.1583, 7.2697) .. (5.28, 7.236).. controls (5.4017, 7.2022) and (5.7367, 7.1307) .. (5.2123, 7.0778).. controls (5.1552, 7.072) and (4.7678, 7.0099) .. (4.5455, 6.976).. controls (4.0318, 6.8976) and (4.4654, 6.5779) .. (4.5288, 6.5421) -- (4.9743, 6.29).. controls (5.1164, 6.2096) and (5.2176, 6.0884) .. (4.9802, 6.0001).. controls (4.6686, 5.884) and (4.5016, 5.8247) .. (4.3235, 5.7179).. controls (4.096, 5.5815) and (4.1892, 5.512) .. (4.3405, 5.4695).. controls (4.536, 5.4146) and (4.7594, 5.3685) .. (4.9609, 5.2602).. controls (5.3252, 5.0645) and (5.1653, 5.1038) .. (4.95, 5.174).. controls (4.3729, 5.3621) and (3.9202, 5.2193) .. (3.5143, 5.1659).. controls (3.2668, 5.1333) and (3.048, 5.3927) .. (3.4505, 5.6539).. controls (3.58, 5.7379) and (3.7402, 5.8187) .. (3.8967, 5.9369).. controls (4.0528, 6.0548) and (4.2673, 6.1713) .. (3.9688, 6.4498).. controls (3.8362, 6.5735) and (3.6723, 6.6741) .. (3.5561, 6.8645).. controls (3.475, 6.9974) and (3.4539, 7.1457) .. (3.6326, 7.238) -- cycle;
        \path[fill=white,line cap=round,line width=0.0132cm] (3.8632, 2.1251).. controls (3.6469, 1.8887) and (3.5803, 1.8837) .. (3.5078, 1.8102).. controls (3.3952, 1.696) and (3.2417, 1.5741) .. (3.4389, 1.3782).. controls (3.5556, 1.2622) and (3.6145, 1.2484) .. (3.682, 1.1948).. controls (3.982, 0.9565) and (3.8225, 0.8739) .. (3.6369, 0.8794) -- (2.9053, 0.9014).. controls (2.3616, 0.9178) and (2.6703, 0.8141) .. (2.836, 0.7284).. controls (3.1449, 0.5684) and (3.5026, 0.5245) .. (3.8286, 0.5503).. controls (4.3701, 0.5933) and (4.4896, 0.6544) .. (4.794, 0.7661).. controls (5.2469, 0.9324) and (5.0677, 1.0458) .. (4.8623, 1.1362) -- (4.3748, 1.3508).. controls (4.0542, 1.492) and (4.2209, 1.7567) .. (4.3642, 1.9068) -- (4.8121, 2.3758).. controls (5.125, 2.7034) and (4.8739, 2.8198) .. (4.7836, 2.9595) -- (3.8009, 2.6692).. controls (4.1236, 2.4566) and (4.0047, 2.2796) .. (3.8632, 2.1251) -- cycle;
        \path[fill=grey6,line cap=round,line width=0.0132cm] (2.7093, 7.0452).. controls (2.6507, 7.0472) and (2.4854, 6.9788) .. (2.2218, 6.844).. controls (1.6132, 6.4746) and (1.3891, 6.0226) .. (1.1337, 5.5774).. controls (1.0331, 5.2655) and (1.0767, 5.1323) .. (1.3115, 5.2357) -- (1.7753, 5.439).. controls (1.9605, 5.5202) and (2.2218, 5.5155) .. (2.2284, 5.1604) -- (2.2397, 4.555).. controls (2.2468, 4.1736) and (2.4586, 3.9656) .. (2.758, 4.0584) -- (3.1815, 4.8929).. controls (3.0516, 4.911) and (2.8984, 4.815) .. (2.7859, 5.0868).. controls (2.7306, 5.2204) and (2.82, 5.5065) .. (2.7898, 5.7813).. controls (2.7734, 5.9302) and (2.8073, 6.1469) .. (2.3323, 6.0732).. controls (2.1684, 6.0477) and (1.7927, 5.9182) .. (2.0443, 6.2926).. controls (2.1766, 6.4895) and (2.3675, 6.6534) .. (2.5569, 6.824).. controls (2.7199, 6.9708) and (2.768, 7.0432) .. (2.7093, 7.0452) -- cycle;
        \path[fill=grey6,line cap=round,line width=0.0132cm] (5.1781, 4.0752).. controls (5.2922, 4.3873) and (5.7235, 4.3942) .. (5.717, 4.0212) -- (5.7051, 3.3395).. controls (5.7002, 3.056) and (5.8679, 3.0217) .. (5.9863, 3.045).. controls (6.2825, 3.1034) and (6.3804, 3.1243) .. (6.5441, 3.1452).. controls (6.9395, 3.1958) and (6.9971, 3.0384) .. (6.9753, 2.8606).. controls (6.9323, 2.5093) and (6.7648, 2.0755) .. (6.2949, 1.6988).. controls (5.7572, 1.2678) and (5.6695, 1.1154) .. (5.9172, 1.6561) -- (6.196, 2.2648).. controls (6.3829, 2.6728) and (6.1159, 2.6109) .. (5.9805, 2.5809).. controls (5.7973, 2.5403) and (5.6399, 2.4249) .. (5.4548, 2.354).. controls (5.0548, 2.2009) and (5.1579, 2.4486) .. (5.1818, 2.5505).. controls (5.2534, 2.8555) and (5.2546, 3.0798) .. (5.257, 3.1567).. controls (5.2628, 3.3427) and (5.2892, 3.4981) .. (4.9902, 3.3126) -- cycle;
        \path[draw=grey6,fill=grey9,line cap=round,line width=0.1058cm] (3.9688, 3.9688) circle (1.214cm);
        \path[draw=black,fill=white,line cap=round,line width=0.0794cm] (3.9688, 3.9688) circle (0.5107cm);
        \path[fill=white,line cap=round,line width=0.1588cm] (1.0953, 6.1799) -- (0.8952, 5.385);
        \path[fill=grey7,line cap=round,line width=0.0265cm] (7.1639, 5.2835).. controls (8.6176, 3.0916) and (6.6702, -0.1716) .. (3.5403, 0.1929).. controls (1.2789, 0.4562) and (-0.6974, 3.1258) .. (1.0283, 5.8072).. controls (-0.7716, 2.4758) and (1.9443, 0.554) .. (3.5392, 0.3308).. controls (5.6842, 0.0306) and (8.6853, 1.9758) .. (7.1639, 5.2835) -- cycle;
    \end{tikzpicture}
\end{center}