[Playlisten] [Impressum und Datenschutzerklärung]

12.01.2 Baum als Datenstruktur


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

ich wollte so einen minimalen – Baukasten in Datenstrukturen – mitgeben – was hatten wir wir hatten das – Püree – eindimensional – zweidimensional – dreidimensional – bestimmen zu achtundneunzig dimensional – als die – bisher billigste Datenstruktur – dann habe ich was erzählt zu Warteschlangenqueues – muss eine Queue eine Warteschlange – eine fast wie ein Eindimensionalray – nur ich kann was in die Warteschlange stellen kann was aus der Warteschlange rausnehmen – und erscheint dann auch nachfragen ob es in der Warteschlange steht das hatten wir – im Seminar – ich hatte den Stack – erwähnt – dem man sich wie ein – Name sagt schon State vorstellen kann ?? gerne andersrum gemalt aber ich finde das man einfach den Stapel so rum vorzustellen – ?? Staffel der auf dem Tisch liegt ?? ich kann oben was drauflegen – und das letzte was ich drauf gelegt habe kann ich wieder unternehmen und wenn das runter genommen ist das vorletzte Unternehmen und so weiter und so fort es Deck wäre – ein – völliger Stuss erzähle – ?? last in first Auto last in first aus der letztere nicht rein lege diese erste Hilfe rausnehmen – und Diktion – ist – first in first aus – der erste der Rhein geht sehr herauskommt – wie – vor dem Schalter in der Warteschlange – das ?? ergänzen das was man – vielleicht die Datenstruktur die man am häufigsten – sieht – man bisschen genauer hin guckt – ist der Baum – ?? – war – ein – Baum besteht aus Ton meinte dass man nicht mit dass wir das noch anders werden ?? – hören – ein Baum besteht aus Knoten – und aus Verbindung dazwischen wie gesagt kann ich mit mal das wird gleich noch anders werden – und zwar so – das es zwischen – jedem Paar von Knoten genau einen Weg gibt und kein anderer – das wäre kein Baum – weil es zwischen den Knoten – und den Knoten kein Weg gibt – das hier wäre kein Baum – weil es zwischen den Knoten – und den Knoten zwei Wege gibt sie können so gehen oder sie können so gehen ein Baum soll heißen zwischen – zwei beliebigen Knoten egal welche – Banknoten sie nehmen – die Piste zwischen eine und genau nur eine Verbindung – super was ich hoffe das würde – ein Baum das sieht für mich aus wie ein Baum darf keine Schleifen haben alles muss verbunden sein und es darf keine Schleifen geben – dass sie erstmals für – Inline noch nicht aus wie ein Baum was hat das – zu tun – typischerweise – gibt es einen bevorzugten – Knoten – die Wurzel – immer noch nicht mit Malik strukturiert immer noch und ich ernenne einen dieser Knoten zur Wurzel zum Beispiel sehen wir – den Knotenende nicht zur Wurzel – und jetzt verbiete ich das ganze ein bisschen – nehmen sie den herum – den hier – ist mir nur auf Knoten und ihre Verbindung angeht – ?? ich den einfachen bisschen rum gehen hier – Knoten ihrer Verbindung stehen Beistrich rum – und – hoffentlich wird es allmählich deutlicher ein Baum ist das die Wurzel des Baums – und – die Knoten die dann – keine weiteren – Kinder mehr haben das wäre – Els ein älterer – singular ein Behälter für diesen Knoten – dieser Knoten wäre ein älter für diese Knoten wurden die keine Kinder mehr haben – sie die Blätter – das hier wäre die Wurzel gut – ?? soll Beistrich vermachen wird Beistrich – dass sie wegmachen so – das ist die Wurzel – ich ernenne also einen von diesen Knoten typischerweise zur Wurzel des Baumes – uns – die – Knoten die keine Kinder haben das werden Blätter – lief – das ist die übliche Schreibweise dann sieht es hoffentlich schon bisschen aus wie ein Baum in der Biologie – man Martin allerdings in Informatik gerne falsch rum mit der Wurzel oben – hören ich hoffe für ?? – gelassen im selben Text – Komma – so stellt man sie ?? vor aus der Wurzel verzweifelt weit verzweigt – bis zu irgendwelchen Blättern hin – nachher in der Praxis sieht man gerne anders auf gemalt in allen Informatikbüchern – an Informatik Websites – an die Wurzel oben – wozu oben – die Wurzel oben und dann verzweigtes – Zweig dieser Baum – dieser Knoten verzweigten zwei Blätter – dieser Knoten hier verzweigt weiterhin zwei Blätter – dieser Knoten – der – von der verzweigten zwei Blättern so sind sie das im typischen Informatiklehrbuch – auf gemalt – ?? gibt sie noch mir – das doch kein plattes sondern dass sich der Knoten ist dennoch Kinder hat weiter dieser Knoten – noch ein Blatt mehr und vielleicht ist dieser Knoten auch kein – kein Blatt sondern hat auch noch Kinder und so weiter sofort – Soma üblicherweise – die Baumstruktur – nie habe ich die Wurzel – die hat ihr zwei Kinder – dieses Kind links hat ein Kind das ist ein Blatt – dieses Kind keinen Platz hat aber zwei Kinder das – wieder Wetter sind und so weiter sofort so sieht der Baum in der Informatik typischerweise – sehen es gibt zwischen zwei beliebigen – Knoten nehmen Sie – diesen Knoten und den Knoten zwischen zwei beliebigen Booten gibt es genau eine Verbindung eine Art von einer zum anderen zu kommen – gibt keine Löcher alle können verbunden werden – und es gibt keine Zyklen – nicht sowas hier können Sie mir Verbindung das macht den Raum aus – wozu Bäume – sich fragen – wozu – in aller Welt brauche ich Bäume – die tauche – hinter die Kulissen in Datenbanken – auf um Datenbanken – schnell zu durchsuchen – ?? man am Beispielplatz – haben Lückentext meines noch Einsatzbasis nicht rein am – wenn es zum Beispiel – darum ginge – Zahlen nach ihrer Größe zu unterteilen – eine Sammlung an Zahlen und ich möchte – nach der Größe – suchen können einer bestimmten Zahl schnell suchen können in der Sammlung dann kann ich meine Sammlung an Zahlen zum Beispiel so in einen Baum einteilen – gegen – achten – fünfzig – hundert und drei – als gegeben diese sieben Zahlen – möchte diesen sieben Zahlen schnell suchen können dann wäre ein Gedanke des sieben Zahlen so zu einem Baum strukturieren – ?? kann ich schnell suchen denn – wenn ich eines – wenn ich wissen will ob die Zahl achtundneunzig – drin steht fange oben an der Wurzel des Baums achtundneunzig – größer als zweiundvierzig – dann suche ich rechts weiter – und finde sofort die achtundneunzig – okay – gefunden – wenn ich Frage ist die – siebzig – in dem in dieser Sammlung von sieben Zahlen ist ?? siebzig Beistrich – oben an siebzig ist größer zwei ?? vierzig if-Verzweigung – ?? rechts rechts stehen die größeren Zahl – ?? sie es kleiner als achtundneunzig – verzweigten Regens – besteht heute fünfzig die siebzig ist also nicht drin – der Baum ist so gebaut – dass ich immer alles was kleiner ist als die Wurzel links habe und alles was größer ist als die Wurzel rechts habe und dass – bei jeder Verzweigung – des Erlaubnis sehr schnell zu suchen ob diesem Fall bestimmt die ganze Zahl enthalten ist oder nicht – dass es mit sieben Zahlen ziemlich schwachsinnig stellen sich vor sie haben einen – etwas vernünftigen – Datenbestand – Millionen – nicht gerade Milliarden oder Millionen – von von Daten zu verwalten – dann entstünde auf der untersten Ebene – auch mit John Smith die Hälfte davon gleich eine Million Daten immer sowas eine Million Daten ?? auf der untersten Ebene zumindest fünf hundert tausend ?? – wenn Sie wissen wollen ob was bestimmtes drin steht eine schlechte Idee diese eine Million Daten alle zu Fuß einzeln durchzugucken – wenn die so einsortiert – haben ein Baum – könnte viel schneller durch gucken – mit dem ersten Schritt hätten sie schon – fünf hundert tausend erledigt von der einen Million mit dem nächsten Schritt hätten sie schon zwo hundert fünfzig tausend erledigt von der Einmündung bei diesem – ganzen Bereich noch hundert fünfzig tausend stehen und so weiter und sofort wird nach jedem Schritt nur noch die Hälfte habe – ich müssen nicht eine Million Vergleiche machen sondern noch den Logarithmus aus einem – also – sowas kommt vorbei – zum Beispiel bei Suchmaschinen Beistrich suchen Indizierung – hinter den Kulissen sobald sie irgendeine Suchanfrage stellt garantiert im Hintergrund irgend so eine Art Baum – das sie wäre ein binärer Baum bei der immer zwei Verzweigungen hat – ganz klassische Art von Baum irgend ein Baum dieser Art steckt hinter allen möglichen – suchen – und suchen zu beschleunigen dass ich nicht – der sich vor Google – Punkt nicht Milliarden Webseiten zu Fuß durch – nach jeder Anfrage das wäre absurd sondern die werden auch in seiner Baumstruktur haben um mit wenigen – Tests – schnell ein Resultat zu – da sind sie wollen – Punkt zwei wo sie Bäume sehen sind in Dateisystem – hat sich so eingebürgert ?? ist das Dateisysteme – Komma die strukturiert sind – sie einfach den Windows Explorer aufmachen – und hier – die Ordneransicht – Anschalten sehen Sie ein Baum – die Wurzel ist jetzt bei mir der Desktop – das ist die Wurzel und der hat mehrere – Kinderlobbys – anscheinend ein Kind öffentlich ein Kind Computer ist ein Kind und so weiter Netzwerksystem – schon das sind alles Kinder – die sehen in dieses eine Kind Komma schon reinkucken was ist unter diesem Kind – drinnen – die ganzen – Datenträger – in diesem Kinds gibt es – diverse – Ordner – also – kleines N – ist ein Kind von Demos und Demos – ist ein Kind von Textdesktop – welche Kinder hatte kleines N – das sind die Kinder von Eckwertesen – insbesondere kommt jetzt da wieder reingucken – eins – ein Knoten dein Kind von einem Kind von einem Kind diesen Sinn was in den Knoten – das sind dann – sinnvollerweise – Blätter die einzelnen Dateien sind Blätter da gibt's dann nicht mehr Weitersaison – sogar trotzdem probieren das – auf zu malen und um klarzumachen dass das – miteinander zu tun hat – Punkt – zweiter – so – also was ist meine Wurzel die Wurzel ist denn – der Desktop ist meine Wurzel – darin gibt es – ein Kind das einzig – mir es gibt ein Kind das nennt sich öffentlich – ich mir das nur zusammen – er – da gibt es ein Kinderfass Computer und so weiter und so weiter und irgendwo gibt es ein Kind das heißt Demos – und so weiter – in den Kinddemos – gibt es einst das Haus quer – Fan – und – andere – Demo Songs vom immer – und so weiter und so weiter – in diesem Kind kleines N gibt es ein – Kind das heißt die Buck – und so weiter und sofort – durch das ganze Dateisystem strukturiert – ?? ein Ort einordnen ?? aber das ist eigentlich Informatik ein Baum – seine – Hierarchie wird automatisch – ein Baum ganz klassisch Anwendung von Dateien von von Bäumen Punkt das ist der zweite große – ?? Punkt – an dem sie Bäume sehen sobald sie mit Dateisystemen – zu tun haben – an mit Bäumen zu tun