{"id":21256,"date":"2021-06-16T19:03:58","date_gmt":"2021-06-16T17:03:58","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=21256"},"modified":"2025-06-12T09:12:19","modified_gmt":"2025-06-12T07:12:19","slug":"binaerer-suchbaum-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/","title":{"rendered":"Bin\u00e4rer Suchbaum (mit Java-Code)"},"content":{"rendered":"\n<p>Es gibt nur eine Datenstruktur, mit der man schnell sowohl Elemente anhand ihres Schl\u00fcssels finden kann \u2013 als auch \u00fcber die Elemente in Schl\u00fcsselreihenfolge iterieren kann: den bin\u00e4ren Suchbaum!<\/p>\n\n\n\n<p>In diesem Artikel erf\u00e4hrst du:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Was ist ein bin\u00e4rer Suchbaum?<\/li>\n\n\n\n<li>Wie f\u00fcgt man neue Elemente ein, wie sucht man sie, und wie l\u00f6scht man sie wieder?  <\/li>\n\n\n\n<li>Wie iteriert man \u00fcber alle Elemente des bin\u00e4ren Suchbaums?<\/li>\n\n\n\n<li>Wie implementiert man einen bin\u00e4ren Suchbaum in Java?<\/li>\n\n\n\n<li>Welche Zeitkomplexit\u00e4t haben die Operationen des bin\u00e4ren Suchbaums?<\/li>\n\n\n\n<li>Was unterscheidet den bin\u00e4ren Suchbaum von \u00e4hnlichen Datenstrukturen?<\/li>\n<\/ul>\n\n\n\n<p>Den Quellcode zum Artikel findest du in diesem&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\" target=\"_blank\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerer-suchbaum-definiton\">Bin\u00e4rer Suchbaum Definiton<\/h2>\n\n\n\n<p>Ein bin\u00e4rer Suchbaum (englisch: <em>binary search tree<\/em>, abgek\u00fcrzt: <em>BST<\/em>) ist ein Bin\u00e4rbaum, dessen Knoten einen Schl\u00fcssel (englisch: <em>key<\/em>) enthalten und in dem der linke Teilbaum eines Knotens nur Schl\u00fcssel enth\u00e4lt, die kleiner (oder gleich) als der Schl\u00fcssel des Elternknotens sind, und der rechte Teilbaum nur Schl\u00fcssel die gr\u00f6\u00dfer (oder gleich) als der Schl\u00fcssel des Elternknotens sind.<\/p>\n\n\n\n<p>Die Datenstruktur des bin\u00e4ren Suchbaums erm\u00f6glicht es schnell\u00b9 Schl\u00fcssel einzuf\u00fcgen, nachzuschlagen und zu entfernen (wie in einem <code>Set<\/code> in Java).<\/p>\n\n\n\n<p>Um einen Knoten zu finden, muss man \u2013 bei der Wurzel beginnend \u2013 den Such-Schl\u00fcssel mit dem Knoten-Schl\u00fcssel vergleichen. Folgende drei F\u00e4lle k\u00f6nnen dabei eintreten:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Der Such-Schl\u00fcssel ist gleich dem Knoten-Schl\u00fcssel: Der Zielknoten ist erreicht.<\/li>\n\n\n\n<li>Der Such-Schl\u00fcssel ist kleiner als der Knoten-Schl\u00fcssel: Die Suche muss im linken Teilbaum forgesetzt werden.<\/li>\n\n\n\n<li>Der Such-Schl\u00fcssel ist gr\u00f6\u00dfer als der Knoten-Schl\u00fcssel: Die Suche muss im rechten Teilbaum forgesetzt werden.<\/li>\n<\/ul>\n\n\n\n<p>Die Knoten k\u00f6nnen neben dem Schl\u00fcssel auch einen Wert (englisch: <em>value<\/em>) enthalten. Dann kann man nicht nur pr\u00fcfen, <em>ob<\/em> der Bin\u00e4re Suchbaum einen Schl\u00fcssel enth\u00e4lt, sondern dem Schl\u00fcssel auch einen Wert zuordnen und diesen \u00fcber den Schl\u00fcssel wieder auslesen (entsprechend einer <code>Map<\/code>).<\/p>\n\n\n\n<p>Die Anordnung der Knoten im Bin\u00e4ren Suchbaum erm\u00f6glicht es au\u00dferdem sehr effizient \u00fcber die Schl\u00fcssel und deren Werte in Schl\u00fcssel-Reihenfolge zu iterieren.<\/p>\n\n\n\n<p class=\"has-background\" style=\"background-color:#f3f8fb\">\u00b9 \"Schnell\" hei\u00dft, dass im besten Fall die Zeitkomplexit\u00e4t <em>O(log n)<\/em> erreicht wird. Mehr dazu in den Abschnitten <a href=\"#Balancierter_binarer_Suchbaum\">Balancierter Bin\u00e4rer Suchbaum<\/a> und <a href=\"#Zeitkomplexitat_des_binaren_Suchbaums\">Zeitkomplexit\u00e4t<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerer-suchbaum-beispiel\">Bin\u00e4rer Suchbaum Beispiel<\/h3>\n\n\n\n<p>Hier siehst du ein Beispiel eines bin\u00e4ren Suchbaums:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"349\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-600x349.png\" alt=\"Bin\u00e4rer Suchbaum \u2013 Beispiel\" class=\"wp-image-21289\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-600x349.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-224x130.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-336x195.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-504x293.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-672x391.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-400x233.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-800x465.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel-944x549.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binaerer-suchbaum-beispiel.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rer Suchbaum \u2013 Beispiel<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Um in diesem Beispiel die 11 zu finden, w\u00fcrde man wie folgt vorgehen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Schritt 1: Vergleich des Such-Schl\u00fcssels 11 mit dem Wurzel-Schl\u00fcssel 5. Die 11 ist gr\u00f6\u00dfer, die Suche muss somit im rechten Teilbaum fortgesetzt werden.<\/li>\n\n\n\n<li>Schritt 2: Vergleich des Such-Schl\u00fcssels 11 mit Knoten-Schl\u00fcssel 9 (rechtes Kind der 5). Die 11 ist gr\u00f6\u00dfer, die Suche muss im rechten Teilbaum unter der 9 fortgesetzt werden.<\/li>\n\n\n\n<li>Schritt 3: Vergleich des Such-Schl\u00fcssels 11 mit Knoten-Schl\u00fcssel 15 (rechtes Kind der 9). Die 11 ist kleiner, die Suche muss im linken Teilbaum unter der 15 fortgesetzt werden.<\/li>\n\n\n\n<li>Schritt 4: Vergleich des Such-Schl\u00fcssels 11 mit Knoten-Schl\u00fcssel 11 (linkes Kind der 15). Der gesuchte Knoten ist gefunden.<\/li>\n<\/ul>\n\n\n\n<p>Im folgenden Diagramm sind die vier Schritte mit blau markierten Knoten und Kanten hervorgehoben:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"350\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-600x350.png\" alt=\"Bin\u00e4rer Suchbaum \u2013 Pfad zum gesuchten Schl\u00fcssel\" class=\"wp-image-21395\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-600x350.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-224x131.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-336x196.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-504x294.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-672x392.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-400x233.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-800x467.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons-944x551.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-example-with-comparisons.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rer Suchbaum \u2013 Pfad zum gesuchten Schl\u00fcssel<\/figcaption><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"eigenschaften-von-binaeren-suchbaeumen\">Eigenschaften von bin\u00e4ren Suchb\u00e4umen<\/h2>\n\n\n\n<p>Die wichtigste Eigenschaft eines Bin\u00e4ren Suchbaums ist der schnelle Zugriff auf einen Knoten \u00fcber dessen Schl\u00fcssel. Der Aufwand hierf\u00fcr h\u00e4ngt von der Struktur des Baumes ab: Knoten, die nahe der Wurzel liegen, werden nach weniger Vergleichen gefunden als Knoten, die weit von der Wurzel entfernt sind. <\/p>\n\n\n\n<p>Je nach Einsatzzweck des bin\u00e4ren Suchbaums ergeben sich unterschiedliche Anforderungen an dessen Form. F\u00fcr bestimmte Einsatzformen soll die H\u00f6he des bin\u00e4ren Suchbaums m\u00f6glichst gering sein (s. Abschnitt <a href=\"#Balancierter_binarer_Suchbaum\">Balancierter bin\u00e4rer Suchbaum<\/a>). <\/p>\n\n\n\n<p>F\u00fcr andere Einsatzformen ist es wichtiger, dass h\u00e4ufig nachgeschlagene Schl\u00fcssel nahe an der Wurzel liegen, w\u00e4hrend die Tiefe von Knoten, auf die seltener zugegriffen wird, weniger ins Gewicht f\u00e4llt (s. Abschnitt <a href=\"#Optimaler_binarer_Suchbaum\">Optimaler bin\u00e4rer Suchbaum<\/a>).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"balancierter-binaerer-suchbaum\">Balancierter bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Ein <em>balancierter bin\u00e4rer Suchbaum<\/em> ist ein bin\u00e4rer Suchbaum, in dem sich die linken und rechten Teilb\u00e4ume eines jeden Knotens in der H\u00f6he um maximal eins unterscheiden.<\/p>\n\n\n\n<p>Der oben gezeigte Beispielbaum ist <em>nicht<\/em> balanciert. Der linke Teilbaum des Knotens \"9\" hat die H\u00f6he eins und der rechte Teilbaum die H\u00f6he drei. Die H\u00f6hendifferenz also gr\u00f6\u00dfer als eins.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"350\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-600x350.png\" alt=\"Nicht balancierter bin\u00e4rer Suchbaum\" class=\"wp-image-21332\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-600x350.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-224x131.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-336x196.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-504x294.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-672x392.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-400x233.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-800x467.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree-944x551.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/unbalanced-binary-search-tree.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Nicht balancierter bin\u00e4rer Suchbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir k\u00f6nnen berechnen, wie viele Vergleiche wir in diesem Baum im Durchschnitt ben\u00f6tigen, um einen Schl\u00fcssel zu finden. Dazu multiplizieren wir auf jeder Knotenebene die Anzahl der Knoten mit der Anzahl der Vergleiche, die wir ben\u00f6tigen, um einen Knoten auf der entsprechenden Ebene zu erreichen:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche<br>(= Knotentiefe + 1)<\/th><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Knoten <br>auf dieser Ebene<\/th><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche<br>auf dieser Ebene<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">1 (Wurzel)<\/td><td class=\"has-text-align-center\" data-align=\"center\">1 (5)<\/td><td class=\"has-text-align-center\" data-align=\"center\">1 \u00d7 1 = 1<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">2 (2, 9)<\/td><td class=\"has-text-align-center\" data-align=\"center\">2 \u00d7 2 = 4<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><td class=\"has-text-align-center\" data-align=\"center\">4 (1, 4, 6, 15)<\/td><td class=\"has-text-align-center\" data-align=\"center\">3 \u00d7 4 = 12<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">4<\/td><td class=\"has-text-align-center\" data-align=\"center\">3 (3, 11, 16)<\/td><td class=\"has-text-align-center\" data-align=\"center\">4 \u00d7 3 = 12<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">5<\/td><td class=\"has-text-align-center\" data-align=\"center\">2 (10, 13)<\/td><td class=\"has-text-align-center\" data-align=\"center\">5 \u00d7 2 = 10<\/td><\/tr><\/tbody><tfoot><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>Summen:<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>12<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>39<\/strong><\/td><\/tr><\/tfoot><\/table><\/figure>\n\n\n\n<p>Wenn wir jeden Knoten genau einmal suchen w\u00fcrden, br\u00e4uchten wir in Summe 39 Vergleiche. 39 Vergleiche geteilt durch 12 Knoten = 3,25 Vergleiche pro Knoten. Im Durchschnitt brauchen wir also 3,25 Vergleiche, um einen Knoten zu finden.<\/p>\n\n\n\n<p>Der folgende Beispielbaum enth\u00e4lt die gleichen Schl\u00fcssel, ist jedoch balanciert:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"275\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-600x275.png\" alt=\"Balancierter bin\u00e4rer Suchbaum\" class=\"wp-image-21335\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-600x275.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-336x154.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-504x231.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-672x308.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-400x183.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-800x367.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree-944x433.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balanced-binary-search-tree.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Balancierter bin\u00e4rer Suchbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir f\u00fchren die gleiche Berechnung f\u00fcr den balancierten Suchbaum durch:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche<br>(= Knotentiefe + 1)<\/th><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Knoten <br>auf dieser Ebene<\/th><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche<br>auf dieser Ebene<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">1 (Wurzel)<\/td><td class=\"has-text-align-center\" data-align=\"center\">1 (5)<\/td><td class=\"has-text-align-center\" data-align=\"center\">1 \u00d7 1 = 1<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">2 (2, 11)<\/td><td class=\"has-text-align-center\" data-align=\"center\">2 \u00d7 2 = 4<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><td class=\"has-text-align-center\" data-align=\"center\">4 (1, 4, 9, 15)<\/td><td class=\"has-text-align-center\" data-align=\"center\">3 \u00d7 4 = 12<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">4<\/td><td class=\"has-text-align-center\" data-align=\"center\">5 (3, 6, 10, 13, 16)<\/td><td class=\"has-text-align-center\" data-align=\"center\">4 \u00d7 5 = 20<\/td><\/tr><\/tbody><tfoot><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>Summen:<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>12<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>37<\/strong><\/td><\/tr><\/tfoot><\/table><\/figure>\n\n\n\n<p>Im balancierten Baum ben\u00f6tigen wir nur noch 37 Vergleiche f\u00fcr 12 Knoten, das sind 3,08 Vergleiche pro Knoten.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"degenerierter-binaerbaum\">Degenerierter Bin\u00e4rbaum<\/h3>\n\n\n\n<p>Die Struktur des bin\u00e4ren Suchbaumes ergibt sich in erster Linie aus der Reihenfolge, in der die Knoten eingef\u00fcgt und gel\u00f6scht werden. Im Extremfall \u2013 wenn die Knoten in auf- oder absteigender Reihenfolge eingef\u00fcgt werden \u2013 k\u00f6nnte ein Baum wie der folgende entstehen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"153\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-600x153.png\" alt=\"Degenerierter Bin\u00e4rbaum\" class=\"wp-image-21352\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-600x153.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-224x57.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-336x86.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-504x129.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-672x171.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-400x102.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-800x204.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree-944x241.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/degenerate-binary-tree.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Degenerierter Bin\u00e4rbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wenn \u2013 wie in diesem Beispiel \u2013 jeder innere Knoten genau ein Kind hat, eine Baumstruktur also gar nicht mehr erkennbar ist, spricht man von einem <em>degenerierten Baum<\/em>.<\/p>\n\n\n\n<p>Wenn wir in diesem Baum jeden Knoten einmal suchen w\u00fcrden, k\u00e4men wir auf<\/p>\n\n\n\n<p class=\"has-text-align-center\">1\u00d71 (f\u00fcr die 1)<br>+ 1\u00d72 (f\u00fcr die 2)<br>+ 1\u00d73 (f\u00fcr die 3)<br>... <br>+ 1\u00d710 (f\u00fcr die 13)<br>+ 1\u00d711 (f\u00fcr die 15)<br><span style=\"text-decoration: underline;\">+ 1\u00d712 (f\u00fcr die 16) <\/span><br>= 78 Vergleiche<\/p>\n\n\n\n<p>... f\u00fcr 12 Knoten. Im Durchschnitt br\u00e4uchten wir also 78 \/ 12 = 6,5 Vergleiche, um einen beliebigen Schl\u00fcssel zu finden \u2013 also deutlich mehr als im zuf\u00e4llig angeordneten und im balancierten Suchbaum.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"selbstbalancierender-binaerer-suchbaum\">Selbstbalancierender bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Ein selbstbalancierender (auch h\u00f6hen-balancierter) bin\u00e4rer Suchbaum kann beim Einf\u00fcgen und L\u00f6schen von Schl\u00fcsseln den Baum so transformieren, dass die H\u00f6he des Baumes m\u00f6glichst klein gehalten wird.<\/p>\n\n\n\n<p>\"M\u00f6glichst klein\" ist dabei nicht n\u00e4her spezifiziert. Ein selbstbalancierender bin\u00e4rer Suchbaum muss also nicht zwingenderweise die Eigenschaften eines <a href=\"#Balancierter_binarer_Suchbaum\">balancierten bin\u00e4ren Suchbaums<\/a> erreichen. (Die H\u00f6hendifferenz des linken und rechten Teilbaum eines Knotens darf also auch gr\u00f6\u00dfer als eins sein.)<\/p>\n\n\n\n<p>Da die Reorganisation des Baumes mit einem gewissen Zeit- und Platz-Overhead verbunden ist, gilt es eine Balance zwischen Aufwand und Ergebnis zu finden. <\/p>\n\n\n\n<p>Es gibt zahlreiche Implementierungen von selbstbalancierenden bin\u00e4ren Suchb\u00e4umen. Zu den bekanntesten geh\u00f6ren der <a href=\"\/de\/algorithmen\/avl-baum-java\/\">AVL-Baum<\/a> und der <a href=\"\/de\/algorithmen\/rot-schwarz-baum-java\/\">Rot-Schwarz-Baum<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"optimaler-binaerer-suchbaum\">Optimaler bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Im oben beschriebenen <a href=\"#Balancierter_binarer_Suchbaum\">balancierten bin\u00e4ren Suchbaum<\/a> werden die durchschnittlichen Kosten f\u00fcr den Zugriff auf <em>beliebige<\/em> Knoten minimiert. Das ist dann sinnvoll, wenn die Suche nach allen Schl\u00fcsseln ann\u00e4hernd gleichverteilt (oder unbekannt) ist.<\/p>\n\n\n\n<p>Es gibt auch Einsatzzwecke, in denen bekannt ist, dass auf bestimmte Knoten \u00f6fter zugegriffen wird als auf andere. Ein Beispiel w\u00e4re ein W\u00f6rterbuch, das zur Rechtschreibkontrolle verwendet wird. Auf die Knoten der h\u00e4ufig genutzten W\u00f6rter wird dabei \u00f6fter zugegriffen als auf die Knoten der selten genutzten W\u00f6rter.<\/p>\n\n\n\n<p>Um die Suchkosten \u2013 also die Anzahl der Vergleiche \u2013 insgesamt zu minimieren, w\u00fcrde es also Sinn machen, Knoten mit h\u00e4ufig benutzten W\u00f6rtern n\u00e4her an der Wurzel zu platzieren als Knoten mit selten genutzten W\u00f6rtern.<\/p>\n\n\n\n<p>Wenn wir im Voraus wissen, wie oft (oder mit welcher Wahrscheinlichkeit) jeder Schl\u00fcssel des bin\u00e4ren Suchbaums gesucht wird, k\u00f6nnen wir den Baum derart konstruieren, dass die Suchkosten f\u00fcr die Gesamtheit der Suchaufrufe minimal sind. Einen solchen Baum bezeichnet man als <em>optimalen bin\u00e4ren Suchbaum<\/em>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Optimaler bin\u00e4rer Suchbaum \u2013 Beispiel<\/h4>\n\n\n\n<p>Das folgende Beispiel zeigt an einem W\u00f6rterbuch mit ein paar W\u00f6rtern und deren H\u00e4ufigkeiten in einem Textkorpus (Quelle: <a rel=\"noopener\" href=\"https:\/\/wacky.sslmit.unibo.it\/doku.php?id=frequency_lists\" target=\"_blank\">WaCky<\/a>), wie sich die Gesamtkosten zwischen balanciertem und optimalen bin\u00e4ren Suchbaum unterscheiden.<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table class=\"has-fixed-layout\"><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Wort<\/th><th class=\"has-text-align-center\" data-align=\"center\">H\u00e4ufigkeit im Textkorpus<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">der<\/td><td class=\"has-text-align-center\" data-align=\"center\">41.943.869<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">die<\/td><td class=\"has-text-align-center\" data-align=\"center\">38.527.491<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">das<\/td><td class=\"has-text-align-center\" data-align=\"center\">11.839.666<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">an<\/td><td class=\"has-text-align-center\" data-align=\"center\">5.932.812<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">mehr<\/td><td class=\"has-text-align-center\" data-align=\"center\">2.332.783<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">zeit<\/td><td class=\"has-text-align-center\" data-align=\"center\">1.163.141<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">euro<\/td><td class=\"has-text-align-center\" data-align=\"center\">568.080<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">eltern<\/td><td class=\"has-text-align-center\" data-align=\"center\">290.303<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">nacht<\/td><td class=\"has-text-align-center\" data-align=\"center\">156.069<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">sehr<\/td><td class=\"has-text-align-center\" data-align=\"center\">85.970<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">plan<\/td><td class=\"has-text-align-center\" data-align=\"center\">59.900<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">los<\/td><td class=\"has-text-align-center\" data-align=\"center\">26.990<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Ein <em>balancierter<\/em> bin\u00e4rer Suchbaum mit den aufgelisteten W\u00f6rten k\u00f6nnte z. B. folgende Struktur haben:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"282\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-600x282.png\" alt=\"W\u00f6rterbuch im balancierten bin\u00e4ren Suchbaum\" class=\"wp-image-21754\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-600x282.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-224x105.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-336x158.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-504x237.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-672x316.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-400x188.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-800x376.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter-944x444.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/balancierter-binaerbaum-woerter.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">W\u00f6rterbuch im balancierten bin\u00e4ren Suchbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Da wir wissen, wie oft die einzelnen W\u00f6rter nachgeschlagen werden, k\u00f6nnen wir die durchschnittlichen Kosten pro Aufruf berechnen:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche (Knotentiefe + 1)<\/th><th class=\"has-text-align-center\" data-align=\"center\">Worth\u00e4ufigkeiten auf dieser Tiefe<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe der Worth\u00e4ufigkeiten auf dieser Tiefe<\/th><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche \u00d7 Summe der Worth\u00e4ufigkeiten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">1 (Wurzel)<\/td><td class=\"has-text-align-center\" data-align=\"center\">568.080 (euro)<\/td><td class=\"has-text-align-center\" data-align=\"center\">568.080<\/td><td class=\"has-text-align-center\" data-align=\"center\">1 \u00d7 568.080 <br>= 568.080<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">41.943.869 (der)<br>+ 156.069 (nacht)<\/td><td class=\"has-text-align-center\" data-align=\"center\">42.099.938<\/td><td class=\"has-text-align-center\" data-align=\"center\">2 \u00d7 42.099.938<br>= 84.199.876<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><td class=\"has-text-align-center\" data-align=\"center\">11.839.666 (das)<br>+ 290.303 (eltern)<br>+ 2.332.783 (mehr)<br>+ 85.970 (sehr)<\/td><td class=\"has-text-align-center\" data-align=\"center\">14.548.722<\/td><td class=\"has-text-align-center\" data-align=\"center\">3 \u00d7 14.548.722<br>= 43.646.166<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">4<\/td><td class=\"has-text-align-center\" data-align=\"center\">5.932.812 (an)<br>+ 38.527.491 (die)<br>+ 26.990 (los)<br>+ 59.900 (plan)<br>+ 1.163.141 (zeit)<\/td><td class=\"has-text-align-center\" data-align=\"center\">45.710.334<\/td><td class=\"has-text-align-center\" data-align=\"center\">4 \u00d7 45.710.334<br>= 182.841.336<\/td><\/tr><\/tbody><tfoot><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>Summen:<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><\/td><td class=\"has-text-align-center\" data-align=\"center\">102.927.074<\/td><td class=\"has-text-align-center\" data-align=\"center\">311.255.458<\/td><\/tr><\/tfoot><\/table><\/figure>\n\n\n\n<p>In diesem balancierten Baum ben\u00f6tigen wir durchschnittlich<\/p>\n\n\n\n<p class=\"has-text-align-center\">311.255.458 \/ 102.927.074 = <strong>3,02 Vergleiche pro Suche<\/strong>.<\/p>\n\n\n\n<p>Es f\u00e4llt auf, dass an der Baumwurzel das relativ selten benutzte Wort \"euro\" liegt. H\u00e4ufig verwendete W\u00f6rter wie \"die\" und \"das\" hingegen liegen relativ weit unten im Baum.<\/p>\n\n\n\n<p>Wenn wir den Baum dahingenend optimieren, dass h\u00e4ufig verwendete W\u00f6rter n\u00e4her an der Wurzel liegen, erreichen wir folgende Struktur:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"463\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-600x463.png\" alt=\"Optimierter bin\u00e4rer Suchbaum\" class=\"wp-image-21759\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-600x463.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-224x173.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-336x259.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-504x389.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-672x519.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-400x309.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-800x617.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2-944x728.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/optimierter-binaerer-suchbaum-v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Optimierter bin\u00e4rer Suchbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Dass dieser Baum nicht mehr balanciert ist, sieht man auf den ersten Blick. Daf\u00fcr liegen die am h\u00e4ufigsten verwendeten W\u00f6rter \"der\", \"die\", \"das\" in den ersten zwei Ebenen des Baumes. Und die am seltensten benutzten W\u00f6rter \"sehr\", \"plan\" und \"los\" befinden sich sehr weit unten.<\/p>\n\n\n\n<p>Berechnen wir noch einmal die durchschnittlichen Kosten:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche (Knotentiefe + 1)<\/th><th class=\"has-text-align-center\" data-align=\"center\">Worth\u00e4ufigkeiten auf dieser Tiefe<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe der Worth\u00e4ufigkeiten auf dieser Tiefe<\/th><th class=\"has-text-align-center\" data-align=\"center\">Anzahl Vergleiche \u00d7 Summe der Worth\u00e4ufigkeiten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">1 (Wurzel)<\/td><td class=\"has-text-align-center\" data-align=\"center\">41.943.869 (der)<\/td><td class=\"has-text-align-center\" data-align=\"center\">41.943.869<\/td><td class=\"has-text-align-center\" data-align=\"center\">1 \u00d7 41.943.869<br>= 41.943.869<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">11.839.666 (das)<br>+ 38.527.491 (die)<\/td><td class=\"has-text-align-center\" data-align=\"center\">50.367.157<\/td><td class=\"has-text-align-center\" data-align=\"center\">2\u00d750.367.157<br>= 100.734.314<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><td class=\"has-text-align-center\" data-align=\"center\">5.932.812 (an)<br>+ 2.332.783 (mehr)<\/td><td class=\"has-text-align-center\" data-align=\"center\">8.265.595<\/td><td class=\"has-text-align-center\" data-align=\"center\">3 \u00d7 8.265.595<br>= 24.796.785<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">4<\/td><td class=\"has-text-align-center\" data-align=\"center\">568.080 (euro)<br>+ 1.163.141 (zeit)<\/td><td class=\"has-text-align-center\" data-align=\"center\">1.731.221<\/td><td class=\"has-text-align-center\" data-align=\"center\">4 \u00d7 1.731.221<br>= 6.924.884<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">5<\/td><td class=\"has-text-align-center\" data-align=\"center\">290.303 (eltern)<br>+ 26.990 (los)<br>+ 156.069 (nacht)<\/td><td class=\"has-text-align-center\" data-align=\"center\">473.362<\/td><td class=\"has-text-align-center\" data-align=\"center\">5 \u00d7 473.362<br>= 2.366.810<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">6<\/td><td class=\"has-text-align-center\" data-align=\"center\">85.970 (sehr)<\/td><td class=\"has-text-align-center\" data-align=\"center\">85.970<\/td><td class=\"has-text-align-center\" data-align=\"center\">6 \u00d7 85.970<br>= 515.820<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">7<\/td><td class=\"has-text-align-center\" data-align=\"center\">59.900 (plan)<\/td><td class=\"has-text-align-center\" data-align=\"center\">59.900<\/td><td class=\"has-text-align-center\" data-align=\"center\">7 \u00d7 59.900<br>= 419.300<\/td><\/tr><\/tbody><tfoot><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>Summen:<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><\/td><td class=\"has-text-align-center\" data-align=\"center\">102.927.074<\/td><td class=\"has-text-align-center\" data-align=\"center\">177.701.782<\/td><\/tr><\/tfoot><\/table><\/figure>\n\n\n\n<p>Im optimalen bin\u00e4ren Suchbaum ben\u00f6tigen wir durchschnittlich<\/p>\n\n\n\n<p class=\"has-text-align-center\">177.701.782 \/ 102.927.074 = <strong>1,73 Vergleiche pro Suche<\/strong>. <\/p>\n\n\n\n<p>Die Suche ist also fast doppelt so schnell wie im balancierten Baum.<\/p>\n\n\n\n<p>Wie ein optimaler bin\u00e4ren Suchbaum konstruiert wird, kannst du z. B. auf <a href=\"https:\/\/www.techiedelight.com\/find-optimal-cost-to-construct-binary-search-tree\/\" target=\"_blank\" rel=\"noopener\">Techie Delight<\/a> nachlesen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerer-suchbaum-in-java\">Bin\u00e4rer Suchbaum in Java<\/h2>\n\n\n\n<p>F\u00fcr die Implementierung des bin\u00e4ren Suchbaums in Java verwenden wir die gleiche grundlegende Datenstruktur wie bei der <a href=\"\/de\/algorithmen\/binaerbaum-java\/#Binarbaum_in_Java\">Java-Implementierung des Bin\u00e4rbaums<\/a>.<\/p>\n\n\n\n<p>Knoten werden in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/Node.java\" target=\"_blank\"><code>Node<\/code><\/a> definiert. Den Schl\u00fcssel speichern wir im Feld <code>data<\/code>. Der Einfachheit halber verwenden wir&nbsp;<code>int<\/code>-Primitive anstatt konkreter oder generischer Klassen.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">Node<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> data;\n  Node left;\n  Node right;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">Node<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> value)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.value = value;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Da wir in diesem Artikel \u2013 und im weiteren Verlauf der Tutorial-Serie \u2013 verschiedene Arten von bin\u00e4ren Suchb\u00e4umen implementieren werden, definieren wir ein Interface <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTree.java\" target=\"_blank\"><code>BinarySearchTree<\/code><\/a>. Dieses erweitert das im ersten Teil der Serie angelegte Interface <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinaryTree.java\" target=\"_blank\"><code>BinaryTree<\/code><\/a> (welches lediglich die Methode <code>getRoot()<\/code> bereitstellt):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">interface<\/span> <span class=\"hljs-title\">BinaryTree<\/span> <\/span>{\n  <span class=\"hljs-function\">Node <span class=\"hljs-title\">getRoot<\/span><span class=\"hljs-params\">()<\/span><\/span>;\n}\n\n<span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">interface<\/span> <span class=\"hljs-title\">BinarySearchTree<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">BinaryTree<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ operations will be added soon...<\/span>\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Im Verlauf dieses Artikels wird das <code>BinarySearchTree<\/code>-Interface von folgenden zwei Klassen implementiert werden: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeIterative.java\" target=\"_blank\" rel=\"noopener\"><code>BinarySearchTreeIterative<\/code><\/a> \u2013 eine iterative Implementierung des bin\u00e4ren Suchbaums<\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java\" target=\"_blank\" rel=\"noopener\"><code>BinarySearchTreeRecursive<\/code><\/a> \u2013 eine rekursive Implementierung des bin\u00e4ren Suchbaums <\/li>\n<\/ul>\n\n\n\n<p>Beide Klassen erweitern <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BaseBinaryTree.java\" target=\"_blank\"><code>BaseBinaryTree<\/code><\/a>, eine Minimal-Implementierung des Bin\u00e4rbaums, die nur die Referenz auf den Wurzelknoten enth\u00e4lt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">BaseBinaryTree<\/span> <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">BinaryTree<\/span> <\/span>{\n  <span class=\"hljs-keyword\">protected<\/span> Node root;\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Node <span class=\"hljs-title\">getRoot<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> root;\n  }\n}\n\n<span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">BinarySearchTreeIterative<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">BaseBinaryTree<\/span>\n    <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">BinarySearchTree<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ operations will be added soon...<\/span>\n}\n\n<span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">BinarySearchTreeRecursive<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">BaseBinaryTree<\/span>\n    <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">BinarySearchTree<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ operations will be added soon...<\/span>\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Das folgende UML-Klassendiagramm zeigt die angelegten Interfaces und Klassen f\u00fcr die Bin\u00e4re-Suchbaum-Datenstruktur:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"307\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-600x307.png\" alt=\"Bin\u00e4rer Suchbaum in Java \u2013 UML-Klassendiagramm\" class=\"wp-image-21652\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-600x307.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-336x172.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-504x258.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-672x344.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-400x205.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-800x409.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml-944x483.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-uml.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rer Suchbaum in Java \u2013 UML-Klassendiagramm<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wundere dich nicht, dass das <code>BinarySearchTree<\/code>-Interface und die implementierenden Klassen noch leer sind \u2013 das wird nicht lange so bleiben. In den folgenden Abschnitten werde ich die verschiedenen Operationen auf bin\u00e4ren Suchb\u00e4umen vorstellen und schrittweise dem Code hinzuf\u00fcgen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"operationen-auf-binaeren-suchbaeumen\">Operationen auf bin\u00e4ren Suchb\u00e4umen<\/h2>\n\n\n\n<p>Bin\u00e4re Suchb\u00e4ume bieten Operationen zum Einf\u00fcgen, L\u00f6schen und Suchen von Schl\u00fcsseln (und ggf. damit verkn\u00fcpften Werten) an, sowie zum Traversieren \u00fcber alle Elemente.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"suche-im-binaeren-suchbaum\">Suche im bin\u00e4ren Suchbaum<\/h3>\n\n\n\n<p>Wie die Suche funktioniert, habe ich in der <a href=\"#Binarer_Suchbaum_Definiton\">Einf\u00fchrung<\/a> und anhand eines <a href=\"#Binarer_Suchbaum_Beispiel\">Beispiels<\/a> detailliert gezeigt. Zusammengefasst: wir vergleichen den Such-Schl\u00fcssel mit den Knoten-Schl\u00fcsseln beginnend an der Wurzel und folgen wiederholt dem linken oder rechten Kindknoten, je nachdem, ob der Such-Schl\u00fcssel kleiner oder gr\u00f6\u00dfer als der jeweilige Knoten-Schl\u00fcssel ist \u2013 solange bis wir den Knoten mit dem gesuchten Schl\u00fcssel gefunden haben. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Suche im bin\u00e4ren Suchbaum \u2013 Java-Quellcode (rekursiv)<\/h4>\n\n\n\n<p>Der Java-Code f\u00fcr die Suche im BST (Abk\u00fcrzung f\u00fcr \"binary search tree\") kann rekursiv und iterativ implementiert werden. Beide Varianten sind unkompliziert. Die rekursive Variante findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L10\" target=\"_blank\" rel=\"noopener\"><code>BinarySearchTreeRecursive<\/code> ab Zeile 10<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Node <span class=\"hljs-title\">searchNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">return<\/span> searchNode(key, root);\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> Node <span class=\"hljs-title\">searchNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key, Node node)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">null<\/span>;\n  }\n\n  <span class=\"hljs-keyword\">if<\/span> (key == node.data) {\n    <span class=\"hljs-keyword\">return<\/span> node;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n    <span class=\"hljs-keyword\">return<\/span> searchNode(key, node.left);\n  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">return<\/span> searchNode(key, node.right);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Der Code sollte selbsterkl\u00e4rend sein.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Suche im bin\u00e4ren Suchbaum \u2013 Java-Quellcode (iterativ)<\/h4>\n\n\n\n<p>Ebenso einfach ist die iterative Variante (<a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeIterative.java#L10\" target=\"_blank\" rel=\"noopener\"><code>BinarySearchTreeIterative<\/code> ab Zeile 10<\/a>). Anstatt die Suche rekursiv auf den Teilb\u00e4umen aufzurufen, wandert die <code>node<\/code>-Referenz entlang der betrachteten Knoten, bis derjenige mit dem gesuchten Schl\u00fcssel gefunden und zur\u00fcckgegeben wird. <\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Node <span class=\"hljs-title\">searchNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  Node node = root;\n  <span class=\"hljs-keyword\">while<\/span> (node != <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">if<\/span> (key == node.data) {\n      <span class=\"hljs-keyword\">return<\/span> node;\n    } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n      node = node.left;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      node = node.right;\n    }\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">null<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"einfuegen-im-binaeren-suchbaum\">Einf\u00fcgen im bin\u00e4ren Suchbaum<\/h3>\n\n\n\n<p>Beim Einf\u00fcgen eines Schl\u00fcssels in den bin\u00e4ren Suchbaum muss sichergestellt werden, dass die Reihenfolge der Schl\u00fcssel erhalten bleibt. Wie genau das erreicht wird, h\u00e4ngt von der konkreten Implementierung ab. Selbstbalancierende bin\u00e4re Suchb\u00e4ume setzen hier komplexe Algorithmen ein, auf die ich in sp\u00e4teren Artikeln der Serie eingehen werde.<\/p>\n\n\n\n<p>Wir implementieren zun\u00e4chst einen <em>nicht<\/em> selbstbalancierenden Suchbaum, der keine Duplikate zul\u00e4sst. Das Einf\u00fcgen neuer Schl\u00fcssel funktioniert wie folgt:<\/p>\n\n\n\n<p>Genau wie bei der Suche folgen wir den Knoten \u2013 beginnend bei der Wurzel \u2013 nach links, wenn der einzuf\u00fcgende Schl\u00fcssel kleiner als der Knoten-Schl\u00fcssel ist, und nach rechts, wenn der einzuf\u00fcgende Schl\u00fcssel gr\u00f6\u00dfer als der Knoten-Schl\u00fcssel ist. Irgendwann erreichen wir einen Blatt-Knoten. Ist der einzuf\u00fcgende Schl\u00fcssel kleiner als der Blatt-Schl\u00fcssel, f\u00fcgen wir einen neuen Knoten als linkes Kind des Blatts ein; ist der einzuf\u00fcgende Schl\u00fcssel gr\u00f6\u00dfer als der Blatt-Schl\u00fcssel, f\u00fcgen wir den neuen Knoten als rechtes Kind ein.<\/p>\n\n\n\n<p>(Sollten wir bei diesem Prozess einen Knoten finden, dessen Schl\u00fcssel der gleiche ist wie der einzuf\u00fcgende Schl\u00fcssel, dann quittieren wir den Einf\u00fcgeversuch mit einer Fehlermeldung. Denn Duplikate sind nicht erlaubt.)<\/p>\n\n\n\n<p>Das folgende Diagramm zeigt, wie wir in den Beispielbaum vom Beginn des Artikels den Schl\u00fcssel 8 einf\u00fcgen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"350\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-600x350.png\" alt=\"Einf\u00fcgen eines Knotens in einen bin\u00e4ren Suchbaum \" class=\"wp-image-21508\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-600x350.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-224x131.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-336x196.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-504x294.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-672x392.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-400x233.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-800x467.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion-944x551.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-insertion.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Einf\u00fcgen eines Knotens in einen bin\u00e4ren Suchbaum <\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die Einf\u00fcge-Operation geht dabei wie folgt vor:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Sie vergleicht die 8 mit dem Wurzel-Schl\u00fcssel 5. Die 8 ist gr\u00f6\u00dfer, sie f\u00e4hrt daher beim rechten Kind der Wurzel, also der 9, fort.<\/li>\n\n\n\n<li>Sie vergleicht die 8 mit der 9. Die 8 ist kleiner, die Operation wandert daher zum linken Kind der 9, also der 6.<\/li>\n\n\n\n<li>Sie vergleicht die 8 mit der 6. Die 8 ist gr\u00f6\u00dfer. Die 6 hat kein rechtes Kind. Die Operation h\u00e4ngt daher einen neuen Knoten mit dem einzuf\u00fcgenden Schl\u00fcssel 8 als rechtes Kind an die 6 an.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Einf\u00fcgen im bin\u00e4ren Suchbaum \u2013 Java-Quellcode (iterativ)<\/h4>\n\n\n\n<p>Auch das Einf\u00fcgen k\u00f6nnen wir sowohl rekursiv als auch iterativ implementieren. Ich beginne mit der iterativen Implementierung. Diese ist zwar etwas l\u00e4nger, daf\u00fcr einfacher zu verstehen als die rekursive Variante. Die iterative Einf\u00fcge-Operation findest du in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeIterative.java#L26\" target=\"_blank\" rel=\"noopener\"><code>BinarySearchTreeIterative<\/code> ab Zeile 26<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">insertNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  Node newNode = <span class=\"hljs-keyword\">new<\/span> Node(key);\n\n  <span class=\"hljs-keyword\">if<\/span> (root == <span class=\"hljs-keyword\">null<\/span>) {\n    root = newNode;\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  Node node = root;\n  <span class=\"hljs-keyword\">while<\/span> (<span class=\"hljs-keyword\">true<\/span>) {\n    <span class=\"hljs-comment\">\/\/ Traverse the tree to the left or right depending on the key<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n      <span class=\"hljs-keyword\">if<\/span> (node.left != <span class=\"hljs-keyword\">null<\/span>) {\n        <span class=\"hljs-comment\">\/\/ Left sub-tree exists --&gt; follow<\/span>\n        node = node.left;\n      } <span class=\"hljs-keyword\">else<\/span> {\n        <span class=\"hljs-comment\">\/\/ Left sub-tree does not exist --&gt; insert new node as left child<\/span>\n        node.left = newNode;\n        <span class=\"hljs-keyword\">return<\/span>;\n      }\n    } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &gt; node.data) {\n      <span class=\"hljs-keyword\">if<\/span> (node.right != <span class=\"hljs-keyword\">null<\/span>) {\n        <span class=\"hljs-comment\">\/\/ Right sub-tree exists --&gt; follow<\/span>\n        node = node.right;\n      } <span class=\"hljs-keyword\">else<\/span> {\n        <span class=\"hljs-comment\">\/\/ Right sub-tree does not exist --&gt; insert new node as right child<\/span>\n        node.right = newNode;\n        <span class=\"hljs-keyword\">return<\/span>;\n      }\n    } <span class=\"hljs-keyword\">else<\/span> {\n      <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"BST already contains a node with key \"<\/span> + key);\n    }\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Wir beginnen mit dem Erstellen des neuen Knotens. Wenn der Wurzelknoten noch nicht gesetzt ist, setzen wir diesen auf den neuen Knoten. <\/p>\n\n\n\n<p>Andernfalls folgen wir in der <code>while<\/code>-Schleife den Knoten von der Wurzel beginnend, bis wir denjenigen Knoten finden, unter dem der neue Knoten als linkes oder rechtes Kind einzuf\u00fcgen ist. Das eigentliche Einf\u00fcgen erledigen wir gleich mit in der Schleife, da wir an der entsprechenden Stelle noch wissen, ob der neue Knoten als linkes oder rechtes Kind eingef\u00fcgt werden soll.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Einf\u00fcgen im bin\u00e4ren Suchbaum \u2013 Java-Quellcode (rekursiv)<\/h4>\n\n\n\n<p>Die deutlich k\u00fcrzere, rekursive L\u00f6sung findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L29\" target=\"_blank\"><code>BinarySearchTreeRecursive<\/code> ab Zeile 29<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">insertNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  root = insertNode(key, root);\n}\n\n<span class=\"hljs-function\">Node <span class=\"hljs-title\">insertNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key, Node node)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ No node at current position --&gt; store new node at current position<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    node = <span class=\"hljs-keyword\">new<\/span> Node(key);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Otherwise, traverse the tree to the left or right depending on the key<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n    node.left = insertNode(key, node.left);\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &gt; node.data) {\n    node.right = insertNode(key, node.right);\n  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"BST already contains a node with key \"<\/span> + key);\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> node;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Bei dieser Variante suchen wir die Einf\u00fcgeposition rekursiv. Die rekursive Methode liefert den <em>neuen<\/em> Knoten zur\u00fcck, wenn die Methode auf einer <code>null<\/code>-Referenz aufgerufen wurde. Der Aufrufer setzt dann die Referenz <code>node.left<\/code> oder <code>node.right<\/code> auf den zur\u00fcckgegebenen Knoten.<\/p>\n\n\n\n<p>Wird die rekursive Methode hingegen auf einem <em>existierenden<\/em> Knoten aufgerufen, wird (nach weiterem Abstieg in und Aufstieg aus der Rekursion) genau dieser wieder zur\u00fcckgegeben. Die Zuweisung zu <code>node.left<\/code> bzw. <code>node.right<\/code> hat in diesem Fall keine \u00c4nderung zur Folge.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"loeschen-im-binaeren-suchbaum\">L\u00f6schen im bin\u00e4ren Suchbaum<\/h3>\n\n\n\n<p>Genau wie beim Einf\u00fcgen von Knoten h\u00e4ngt auch beim L\u00f6schen die konkrete Vorgehensweise von der Implementation ab. Selbstbalancierende Suchb\u00e4ume verwenden komplexe Algorithmen, um die Balance aufrechtzuerhalten. Wir implementieren zun\u00e4chst eine einfache L\u00f6sung. Dabei m\u00fcssen wir \u2013 wie auch bei Bin\u00e4rb\u00e4umen im Allgemeinen \u2013 drei F\u00e4lle unterscheiden:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall A: Knoten ohne Kinder (Blatt) l\u00f6schen  <\/h4>\n\n\n\n<p>Liegt der zu l\u00f6schende Schl\u00fcssel auf einem Blatt, dann k\u00f6nnen wir dieses einfach aus dem Baum entfernen. Die Reihenfolge der restlichen Knoten \u00e4ndert sich dadurch nicht. Dazu setzen wir die <code>left<\/code>- oder <code>right<\/code>-Referenz des Elternknotens, die auf den zu l\u00f6schenden Knoten zeigt, auf <code>null<\/code>.<\/p>\n\n\n\n<p>Im folgenden Beispiel entfernen wir die den Knoten mit dem Schl\u00fcssel 10 aus dem Beispielbaum dieses Artikels. Das Diagramm zeigt der \u00dcbersicht halber nur den rechten Teilbaum an:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"275\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-600x275.png\" alt=\"Knoten ohne Kinder (Blatt) aus bin\u00e4rem Suchbaum l\u00f6schen\" class=\"wp-image-21562\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-600x275.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-336x154.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-504x231.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-672x308.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-400x183.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-800x367.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2-944x433.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-leaf-v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Knoten ohne Kinder (Blatt) aus bin\u00e4rem Suchbaum l\u00f6schen<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Fall B: Knoten mit einem Kind (Halbblatt) l\u00f6schen<\/h4>\n\n\n\n<p>Wollen wir einen Knoten im bin\u00e4ren Suchbaum l\u00f6schen, der genau ein Kind hat, dann r\u00fcckt das Kind an die gel\u00f6schte Position auf. Auch dabei bleibt die Reihenfolge aller anderen Knoten erhalten. <\/p>\n\n\n\n<p>Das folgende Beispiel zeigt, wie wir nach dem L\u00f6schen der 10 im vorherigen Schritt nun auch den Knoten mit dem Schl\u00fcssel 11 l\u00f6schen. Wir setzen die <code>left<\/code>- oder <code>right<\/code>-Referenz des Elternknotens (im Beispiel 15) auf das Kind des gel\u00f6schten Knotens (im Beispiel 13).<\/p>\n\n\n\n<p>Die 13 r\u00fcckt dadurch an die gel\u00f6schte Position auf:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"275\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-600x275.png\" alt=\"Knoten mit einem Kind (Halbblatt) aus bin\u00e4rem Suchbaum l\u00f6schen\" class=\"wp-image-21560\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-600x275.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-336x154.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-504x231.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-672x308.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-400x183.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-800x367.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf-944x433.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-half-leaf.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Knoten mit einem Kind (Halbblatt) aus bin\u00e4rem Suchbaum l\u00f6schen<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Fall C: Knoten mit zwei Kindern l\u00f6schen<\/h4>\n\n\n\n<p>Wenn wir einen Knoten aus einem bin\u00e4ren Suchbaum l\u00f6schen wollen, der zwei Kinder hat, wird es etwas komplizierter. Ein verbreiteter Ansatz ist der folgende:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Wir ermitteln im rechten Teilbaum den Knoten mit dem kleinsten Schl\u00fcssel. Dies ist der sogenannte \"In-order-Nachfolger\" des zu l\u00f6schenden Knotens.<\/li>\n\n\n\n<li>Wir kopieren die Daten des In-order-Nachfolgers in den zu l\u00f6schenden Knoten.<\/li>\n\n\n\n<li>Wir entfernen den In-order-Nachfolger aus dem rechten Teilbaum. Da dies der Knoten mit dem kleinsten Schl\u00fcssel des rechten Teilbaums ist, kann er kein linkes Kind haben. Er hat also entweder gar kein Kind oder nur ein rechtes.  Entsprechend k\u00f6nnen wir den In-order-Nachfolger wie in Fall A oder B entfernen.<\/li>\n<\/ol>\n\n\n\n<p>Im folgenden Beispiel l\u00f6schen wir den Wurzelknoten 5, indem In-order-Nachfolger 6 dessen Position einnimmt:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"275\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-800x275.png\" alt=\"Knoten mit zwei Kindern aus bin\u00e4rem Suchbaum l\u00f6schen\" class=\"wp-image-21557\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-800x275.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-224x77.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-336x116.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-504x173.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-672x231.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-400x138.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-600x206.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-944x325.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode-1200x413.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/delete-node-from-binary-search-tree-inode.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Knoten mit zwei Kindern aus bin\u00e4rem Suchbaum l\u00f6schen<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Alternativ kann nat\u00fcrlich auch der In-order-<em>Vorg\u00e4nger<\/em> des <em>linken<\/em> Teilbaums an die Stelle des gel\u00f6schten Knotens tretens. Eine intelligente Auswahl von In-order-Vorg\u00e4nger oder -Nachfolger erh\u00f6ht die Wahrscheinlichkeit, dass der Baum einigerma\u00dfen ausbalanciert wird (und bleibt).<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">L\u00f6schen im bin\u00e4ren Suchbaum \u2013 Java-Quellcode (rekursiv)<\/h4>\n\n\n\n<p>Wie alle anderen Operationen, kann auch das L\u00f6schen aus dem bin\u00e4ren Suchbaum rekursiv und iterativ implementiert werden. Wenn Du die rekusive Methode zum Einf\u00fcgen verstanden hast, wird es einfacher sein, auch beim L\u00f6schen mit der rekursiven Methode zu beginnen. Du findest sie in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L52\" target=\"_blank\" rel=\"noreferrer noopener\"><code>BinarySearchTreeRecursive<\/code> ab Zeile 52<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">deleteNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  root = deleteNode(key, root);\n}\n\n<span class=\"hljs-function\">Node <span class=\"hljs-title\">deleteNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key, Node node)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ No node at current position --&gt; go up the recursion<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">null<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Traverse the tree to the left or right depending on the key<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n    node.left = deleteNode(key, node.left);\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &gt; node.data) {\n    node.right = deleteNode(key, node.right);\n  }\n\n  <span class=\"hljs-comment\">\/\/ At this point, \"node\" is the node to be deleted<\/span>\n\n  <span class=\"hljs-comment\">\/\/ Node has no children --&gt; just delete it<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.left == <span class=\"hljs-keyword\">null<\/span> &amp;&amp; node.right == <span class=\"hljs-keyword\">null<\/span>) {\n    node = <span class=\"hljs-keyword\">null<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node has only one child --&gt; replace node by its single child<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.left == <span class=\"hljs-keyword\">null<\/span>) {\n    node = node.right;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.right == <span class=\"hljs-keyword\">null<\/span>) {\n    node = node.left;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node has two children<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    deleteNodeWithTwoChildren(node);\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> node;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>In den ersten Zeilen (bis zum Kommentar <em>\"At this point...\"<\/em>) suchen wir die L\u00f6schposition, indem wir die L\u00f6schmethode rekursiv aufrufen, wenn der zu l\u00f6schende Schl\u00fcssel kleiner oder gr\u00f6\u00dfer als der des gerade betrachteten Knotens ist.<\/p>\n\n\n\n<p>Haben wir den zu l\u00f6schenden Knoten gefunden und hat dieser keine Kinder, gibt die Methode <code>null<\/code> zur\u00fcck. Der Aufrufer setzt dann die <code>left<\/code>- oder <code>right<\/code>-Referenz des Parent-Knotens entsprechend auf <code>null<\/code>.<\/p>\n\n\n\n<p>Hat der zu l\u00f6schende Knoten genau ein Kind, wird eben dieses Kind zur\u00fcckgegeben. Der Aufrufer setzt die <code>left<\/code>- oder <code>right<\/code>-Referenz des Parent-Knotens auf das zur\u00fcckgegebene Kind. Als Folge dessen ist der zu l\u00f6schende Knoten aus dem Baum entfernt.<\/p>\n\n\n\n<p>Hat der zu l\u00f6schende Knoten zwei Kinder, wird die folgende Methode aufgerufen:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-10\" data-shcb-language-name=\"GLSL\" data-shcb-language-slug=\"glsl\"><span><code class=\"hljs language-glsl\">private <span class=\"hljs-type\">void<\/span> deleteNodeWithTwoChildren(Node node) {\n  <span class=\"hljs-comment\">\/\/ Find minimum node of right subtree (\"inorder successor\" of current node)<\/span>\n  Node inOrderSuccessor = findMinimum(node.right);\n\n  <span class=\"hljs-comment\">\/\/ Copy inorder successor's data to current node<\/span>\n  node.data = inOrderSuccessor.data;\n\n  <span class=\"hljs-comment\">\/\/ Delete inorder successor recursively<\/span>\n  node.right = deleteNode(inOrderSuccessor.data, node.right);\n}\n\nprivate Node findMinimum(Node node) {\n  <span class=\"hljs-keyword\">while<\/span> (node.left != null) {\n    node = node.left;\n  }\n  <span class=\"hljs-keyword\">return<\/span> node;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-10\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">GLSL<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">glsl<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Zuerst wird \u00fcber die <code>findMinimum()<\/code>-Methode der In-order-Nachfolger gesucht. Dessen Daten werden in den zu l\u00f6schenden Knoten kopiert. Danach wird der In-order-Nachfolger durch rekursiven Aufruf von <code>deleteNode()<\/code> aus dem rechten Teilbaum des zu l\u00f6schenden Knoten entfernt.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">L\u00f6schen im bin\u00e4ren Suchbaum \u2013 Java-Quellcode (iterativ)<\/h4>\n\n\n\n<p>Die iterative Methode ist deutlich l\u00e4nger, da wir zum L\u00f6schen des In-order-Nachfolgers nicht einfach die L\u00f6sch-Methode rekursiv aufrufen k\u00f6nnen. Du findest die iterative Implementierung in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeIterative.java#L62\" target=\"_blank\" rel=\"noreferrer noopener\"><code>BinarySearchTreeIterative<\/code> ab Zeile 62<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-11\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">deleteNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  Node node = root;\n  Node parent = <span class=\"hljs-keyword\">null<\/span>;\n\n  <span class=\"hljs-comment\">\/\/ Find the node to be deleted<\/span>\n  <span class=\"hljs-keyword\">while<\/span> (node != <span class=\"hljs-keyword\">null<\/span> &amp;&amp; node.data != key) {\n    <span class=\"hljs-comment\">\/\/ Traverse the tree to the left or right depending on the key<\/span>\n    parent = node;\n    <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n      node = node.left;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      node = node.right;\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node not found?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ At this point, \"node\" is the node to be deleted<\/span>\n\n  <span class=\"hljs-comment\">\/\/ Node has at most one child --&gt; replace node by its single child<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node.left == <span class=\"hljs-keyword\">null<\/span> || node.right == <span class=\"hljs-keyword\">null<\/span>) {\n    deleteNodeWithZeroOrOneChild(key, node, parent);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node has two children<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    deleteNodeWithTwoChildren(node);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-11\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>In der ersten H\u00e4lfte der Methode (bis zum Kommentar <em>\"At this point...\"<\/em>) wird \u2013 genau wie beim iterativen Suchen und Einf\u00fcgen \u2013 der zu l\u00f6schende Knoten gesucht. Dabei merken wir uns dessen Elternknoten.<\/p>\n\n\n\n<p>Ein Blatt oder Halbblatt wird dann mit der Methode <code>deleteNodeWithZeroOrOneChild()<\/code> entfernt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-12\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">deleteNodeWithZeroOrOneChild<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key, Node node, Node parent)<\/span> <\/span>{\n  Node singleChild = node.left != <span class=\"hljs-keyword\">null<\/span> ? node.left : node.right;\n\n  <span class=\"hljs-keyword\">if<\/span> (node == root) {\n    root = singleChild;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &lt; parent.data) {\n    parent.left = singleChild;\n  } <span class=\"hljs-keyword\">else<\/span> {\n    parent.right = singleChild;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-12\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Je nachdem, ob der zu l\u00f6schende Knoten linkes oder rechtes Kind seines Parents ist, wird die <code>left<\/code>- oder <code>right<\/code>-Referenz des Parents auf das verbleibende Kind des zu l\u00f6schenden Knotens gesetzt. Hat der zu l\u00f6schende Knoten <em>kein<\/em> Kind, dann ist <code>child<\/code> gleich <code>null<\/code>, und entsprechend wird auch die <code>left<\/code>- oder <code>right<\/code>-Referenz des Parents auf <code>null<\/code> gesetzt.<\/p>\n\n\n\n<p>Hat der zu l\u00f6schende Knoten zwei Kinder, dann wird die Methode <code>deleteNodeWithTwoChildren()<\/code> aufgerufen:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-13\" data-shcb-language-name=\"GLSL\" data-shcb-language-slug=\"glsl\"><span><code class=\"hljs language-glsl\">private <span class=\"hljs-type\">void<\/span> deleteNodeWithTwoChildren(Node node) {\n  <span class=\"hljs-comment\">\/\/ Find minimum node of right subtree (\"inorder successor\" of current node)<\/span>\n  Node inOrderSuccessor = node.right;\n  Node inOrderSuccessorParent = node;\n  <span class=\"hljs-keyword\">while<\/span> (inOrderSuccessor.left != null) {\n    inOrderSuccessorParent = inOrderSuccessor;\n    inOrderSuccessor = inOrderSuccessor.left;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Copy inorder successor's data to current node<\/span>\n  node.data = inOrderSuccessor.data;\n\n  <span class=\"hljs-comment\">\/\/ Delete inorder successor<\/span>\n\n  <span class=\"hljs-comment\">\/\/ Case a) Inorder successor is the deleted node's right child<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (inOrderSuccessor == node.right) {\n    <span class=\"hljs-comment\">\/\/ --&gt; Replace right child with inorder successor's right child<\/span>\n    node.right = inOrderSuccessor.right;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Case b) Inorder successor is further down, meaning, it's a left child<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-comment\">\/\/ --&gt; Replace inorder successor's parent's left child<\/span>\n    <span class=\"hljs-comment\">\/\/     with inorder successor's right child<\/span>\n    inOrderSuccessorParent.left = inOrderSuccessor.right;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-13\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">GLSL<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">glsl<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Wie auch bei der rekursiven Variante wird zun\u00e4chst der In-order-Nachfolger gesucht und dessen Daten in den zu l\u00f6schenden Knoten kopiert.<\/p>\n\n\n\n<p>Das Entfernen des In-order-Nachfolgers aus dem rechten Teilbaum ist in der iterativen Variante allerdings aufw\u00e4ndiger. Hier m\u00fcssen zwei F\u00e4lle unterschieden werden:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Der In-order-Nachfolger ist das rechte Kind des zu l\u00f6schenden Knotens, also die Wurzel des rechten Teilbaums. In diesem Fall wird das rechte Kind des zu l\u00f6schenden Knotens mit dem rechten Kind des In-order-Nachfolgers ersetzt.<\/li>\n\n\n\n<li>Der In-order-Nachfolger ist weiter unten im rechten Teilbaum. In diesem Fall ist er das linke Kind seines Eltern-Knotens und wird durch sein eigenes rechtes Kind ersetzt.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"traversierung-des-binaeren-suchbaums\">Traversierung des bin\u00e4ren Suchbaums<\/h3>\n\n\n\n<p>Genau wie bei Bin\u00e4rb\u00e4umen im Allgemeinen k\u00f6nnen auch in einem bin\u00e4ren Suchbaum Pre-order-, Post-order-, In-order-, Reverse-in-order- und Level-order-Traversierungen durchgef\u00fchrt werden.<\/p>\n\n\n\n<p>Was diese Traversierungsarten bedeuten und wie sie in Java implementiert werden, erf\u00e4hrst du im Abschnitt <a href=\"\/de\/algorithmen\/binaerbaum-java\/#Binarbaum-Traversierung\">Bin\u00e4rbaum-Traversierung<\/a> des Artikels \u00fcber Bin\u00e4rb\u00e4ume.<\/p>\n\n\n\n<p>W\u00e4hrend pre-, post- und level-order wenig sinnvoll sind, ist die In-order-Traversierung im bin\u00e4ren Suchbaum \u00e4u\u00dferst hilfreich: sie iteriert \u00fcber alle Knoten des Baumes in Sortierreihenfolge ihrer Schl\u00fcssel:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"376\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-600x376.png\" alt=\"In-order-Traversierung im bin\u00e4ren Suchbaum\" class=\"wp-image-21711\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-600x376.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-336x211.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-504x316.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-672x421.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-400x251.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-800x501.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal-944x592.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-in-order-traversal.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">In-order-Traversierung im bin\u00e4ren Suchbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die im vorangegangenen Artikel vorgestellten Traversierungsklassen <code><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversal.java\" data-type=\"URL\" target=\"_blank\" rel=\"noopener\">DepthFirstTraversal<\/a><\/code>, <code><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java\" target=\"_blank\" rel=\"noopener\">DepthFirstTraversalIterative<\/a><\/code> und <code><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java\" target=\"_blank\" rel=\"noopener\">DepthFirstTraversalRecursive<\/a><\/code> k\u00f6nnen unver\u00e4ndert auf Instanzen von <code>BinarySearchTree<\/code> angewendet werden, da dieser ja transitiv das Interface <code>BinaryTree<\/code> implementiert. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaeren-suchbaum-validieren\">Bin\u00e4ren Suchbaum validieren<\/h3>\n\n\n\n<p>Es gibt Situationen, in denen wir einen Bin\u00e4rbaum vorliegen haben und wir pr\u00fcfen m\u00fcssen, ob dieser ein valider bin\u00e4rer Suchbaum ist.<\/p>\n\n\n\n<p>Die naheliegende L\u00f6sung \u2013 rekursiv zu pr\u00fcfen, ob jeder Knoten gr\u00f6\u00dfer als sein linkes Kind und kleiner als sein rechtes Kind ist \u2013 ist leider falsch. Denn diese Eigenschaft w\u00fcrde beispielsweise auch auf folgenden Bin\u00e4rbaum zutreffen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"198\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-400x198.png\" alt=\"Kein bin\u00e4rer Suchbaum\" class=\"wp-image-21570\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-400x198.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-224x111.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-336x166.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-504x249.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-672x333.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst-600x297.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/not-a-bst.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Kein bin\u00e4rer Suchbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die 6 ist in diesem Beispiel kleiner als die 12 \u2013 so weit, so gut. Sie befindet sich allerdings im rechten Teilbaum unter der 8. Dieser Teilbaum darf nur Schl\u00fcssel enthalten, die gr\u00f6\u00dfer als 8 sind. Da dies auf die 6 nicht zutrifft, sind die Anforderungen f\u00fcr einen validen BST nicht erf\u00fcllt. <\/p>\n\n\n\n<p>Wir haben stattdessen zwei M\u00f6glichkeiten:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Wir f\u00fchren ein regul\u00e4res Pre-order-Traversal durch und pr\u00fcfen dabei, ob die Schl\u00fcsselreihenfolge eingehalten wird, d. h. ob der Schl\u00fcssel eines Knotens gr\u00f6\u00dfer (oder gleich) ist wie der Schl\u00fcssel des Vorg\u00e4ngerknotens.<\/li>\n\n\n\n<li>Wir pr\u00fcfen \u2013 von der Wurzel beginnend \u2013 den linken und rechten Teilbaum eines jeden Knoten rekursiv und geben dabei einen Bereich von Schl\u00fcssel an, die in diesem Teilbaum vorkommen d\u00fcrfen.<\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\">Bin\u00e4ren Suchbaum validieren \u2013 Java-Quellcode<\/h4>\n\n\n\n<p>Die zweite Variante l\u00e4sst sich am einfachsten durch Lesen des Quellcodes verstehen (Klasse <code><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeValidator.java\" target=\"_blank\" rel=\"noopener\">BinarySearchTreeValidator<\/a><\/code>). Die folgende Variante erlaubt keine Schl\u00fcssel-Duplikate:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-14\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isBstWithoutDuplicates<\/span><span class=\"hljs-params\">(BinaryTree tree)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">return<\/span> isBstWithoutDuplicates(tree.root, Integer.MIN_VALUE, Integer.MAX_VALUE);\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isBstWithoutDuplicates<\/span><span class=\"hljs-params\">(\n    Node node, <span class=\"hljs-keyword\">int<\/span> minAllowedKey, <span class=\"hljs-keyword\">int<\/span> maxAllowedKey)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">true<\/span>;\n  }\n\n  <span class=\"hljs-keyword\">if<\/span> (node.data &lt; minAllowedKey || node.data &gt; maxAllowedKey) {\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">false<\/span>;\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> isBstWithoutDuplicates(node.left, minAllowedKey, node.data - <span class=\"hljs-number\">1<\/span>)\n      &amp;&amp; isBstWithoutDuplicates(node.right, node.data + <span class=\"hljs-number\">1<\/span>, maxAllowedKey);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-14\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Wir \u00fcbergeben der rekursiven <code>isBstWithoutDuplicates()<\/code>-Methode zun\u00e4chst den Wurzelknoten und den Zahlenbereich aller Integer-Werte. Die Methode pr\u00fcft, ob der Schl\u00fcssel des \u00fcbergebenen Knotens im erlaubten Zahlenbereich liegt. Wenn nicht, gibt die Methode <code>false<\/code> zur\u00fcck.<\/p>\n\n\n\n<p>Wenn ja, wird die Methode rekursiv auf dem linken und rechten Teilbaum aufgerufen. Dabei wird der erlaubte Zahlenbereich entsprechend der BST-Eigenschaften immer weiter eingeschr\u00e4nkt.<\/p>\n\n\n\n<p>Eine zweite Variante der Methode, die auch Schl\u00fcssel-Duplikate erlaubt findest du <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeValidator.java#L33\" target=\"_blank\">in derselben Klasse ab Zeile 33<\/a>. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-des-binaeren-suchbaums\">Zeitkomplexit\u00e4t des bin\u00e4ren Suchbaums<\/h2>\n\n\n\n<p>Der Aufwand f\u00fcr das Suchen, Einf\u00fcgen, und L\u00f6schen steigt linear mit der Tiefe des jeweiligen Knotens, da f\u00fcr jede Ebene, die der Knoten von der Wurzel entfernt ist, ein Vergleich durchgef\u00fchrt werden muss.<\/p>\n\n\n\n<p>In einem <a href=\"#Balancierter_Binarer_Suchbaum\">balancierten Bin\u00e4rbaum<\/a> kann bei jedem Vergleich ungef\u00e4hr die H\u00e4lfte des Baumes verworfen werden. Die H\u00f6he eines balancierten Bin\u00e4rbaums mit <em>n<\/em> Knoten \u2013 und damit auch die Zeitkomplexit\u00e4t f\u00fcr die Such-, Einf\u00fcge- und L\u00f6schoperation \u2013 liegt also in der Gr\u00f6\u00dfenordnung <em>O(log&nbsp;n)<\/em>.<\/p>\n\n\n\n<p>In einem <a href=\"#Degenerierter_Binarbaum\">degenerierten Bin\u00e4rbaum<\/a> entspricht die H\u00f6he der Anzahl der Knoten. Die Anzahl der Vergleiche \u2013 und damit auch die Zeitkomplexit\u00e4t f\u00fcr alle Operationen \u2013 liegt somit in der Gr\u00f6\u00dfenordnung <em>O(n)<\/em>.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" nowprocket><\/script><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerer-suchbaum-im-vergleich\">Bin\u00e4rer Suchbaum im Vergleich<\/h2>\n\n\n\n<p>In den folgenden Abschnitten findest du die Vor- und Nachteile des Bin\u00e4ren Suchbaums gegen\u00fcber anderen Datenstrukturen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerbaum-vs-binaerer-suchbaum\">Bin\u00e4rbaum vs. bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Der Bin\u00e4re Suchbaum ist eine Sonderform des Bin\u00e4rbaums, in dem die Bin\u00e4rbaum-Eigenschaften (s. <a href=\"#Binarer_Suchbaum_Definiton\">Definiton<\/a>) erf\u00fcllt sind. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerer-suchbaum-vs-heap\">Bin\u00e4rer Suchbaum vs. Heap<\/h3>\n\n\n\n<p>Im folgenden Vergleich von bin\u00e4rem Suchbaum und <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/heapsort\/#Was_ist_ein_Heap\">Heap<\/a> gehe ich von einem <em>balancierten<\/em> bin\u00e4ren Suchbaum aus. Bei einem degenerierten bin\u00e4ren Suchbaum sind die angegebenen Zeitkomplexit\u00e4ten entsprechend schlechter, n\u00e4mlich <em>O(n)<\/em>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In einem bin\u00e4ren Suchbaum kann \u00fcber die Schl\u00fcssel in Sortierreihenfolge iteriert werden. Das ist in einem Heap nicht direkt m\u00f6glich.<\/li>\n\n\n\n<li>Einf\u00fcgen und L\u00f6schen von Elementen ist in beiden Datenstrukturen mit logarithmischen Aufwand \u2013 <em>O(log\u00a0n)<\/em> \u2013 m\u00f6glich.<\/li>\n\n\n\n<li>Die Suche nach einem Element ist im bin\u00e4ren Suchbaum mit logarithmischen Aufwand \u2013 <em>O(log\u00a0n)<\/em> \u2013 verbunden. Da der Heap nicht sortiert ist, bleibt nur ein Durchsuchen aller Elemente \u2013 also linearer Aufwand, <em>O(n)<\/em>.<\/li>\n\n\n\n<li>In einem Heap kann mit konstantem Aufwand \u2013 <em>O(1)<\/em> \u2013 auf das gr\u00f6\u00dfte (Max-Heap) oder kleinste (Min-Heap) Element zugegriffen werden. In einem bin\u00e4ren Suchbaum muss dazu entweder allen linken oder allen rechten Kindern gefolgt werden, was logarithmischen Aufwand \u2013 <em>O(log\u00a0n)<\/em> \u2013 erfordert. <\/li>\n\n\n\n<li>Der Aufbau eines Heaps kann in linearer Zeit \u2013 <em>O(n)<\/em> erfolgen \u2013 der Aufbau eines BST hat einen Aufwand von <em>O(n log n)<\/em>.<\/li>\n<\/ul>\n\n\n\n<p>Wann sollte also welche Datenstruktur verwendet werden?<\/p>\n\n\n\n<p>M\u00f6chte man nach Elementen suchen oder \u00fcber alle Elemente in Sortierreihenfolge iterieren, eignet sich der bin\u00e4re Suchbaum. Interessiert man sich hingegen nur f\u00fcr das gr\u00f6\u00dfte oder kleinste Element, eignet sich der Heap besser. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerer-suchbaum-vs-hashtable\">Bin\u00e4rer Suchbaum vs. Hashtable<\/h3>\n\n\n\n<p>Ich gehe auch in diesem Vergleich von einem <em>balancierten<\/em> bin\u00e4ren Suchbaum aus. <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Hashtabelle\" target=\"_blank\">Hashtable<\/a> bezeichnet hier die abstrakte Datenstruktur. Der Vergleich gilt z. B. auch f\u00fcr die konkreten Java-Typen <code>HashMap<\/code> und <code>HashSet<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In einem bin\u00e4ren Suchbaum kann \u00fcber die Schl\u00fcssel in Sortierreihenfolge iteriert werden. Dies ist in einer Hashtable nicht m\u00f6glich.<\/li>\n\n\n\n<li>In einem bin\u00e4ren Suchbaum ist eine Bereichssuche m\u00f6glich (also die Suche nach allen Elementen, die in einem vorgegebenen Wertebereich liegen). Da die Hashtable unsortiert ist, ist das bei ihr nicht m\u00f6glich.<\/li>\n\n\n\n<li>In einer Hashtable k\u00f6nnen nur Elemente gespeichert werden, f\u00fcr die eine Hashfunktion definiert ist. In einem bin\u00e4ren Suchbaum k\u00f6nnen nur Elemente gespeichert werden, f\u00fcr die eine Vergleichsfunktion definiert ist.<\/li>\n\n\n\n<li>In einer Hashtable kann es zu \"Bucket Collisions\" kommen. Diese m\u00fcssen mit (mehr oder weniger) aufw\u00e4ndigen Algorithmen sowohl beim Einf\u00fcgen als auch bei der Suche aufgel\u00f6st werden.<\/li>\n\n\n\n<li>Einf\u00fcgen, Suchen und L\u00f6schen sind in einer Hashtable mit konstantem Aufwand \u2013 <em>O(1)<\/em> \u2013 m\u00f6glich, sofern die Hashtable ausreichend dimensioniert ist und eine geeignete Hashfunktion verwendet wird. Beim bin\u00e4ren Suchbaum ist die Zeitkomplexit\u00e4t f\u00fcr alle drei Operationen <em>O(log\u00a0n)<\/em>. Moderne Hashtables verwenden innerhalb ihrer Buckets ebenfalls bin\u00e4re Suchb\u00e4ume, sodass die Zeitkomplexit\u00e4t bei vielen Kollisionen ebenfalls Richtung <em>O(log\u00a0n)<\/em> geht.<\/li>\n\n\n\n<li>Ein bin\u00e4rer Suchbaum ist effizienter bzgl. des Platzbedarfs, da er pro Element genau einen Knoten enth\u00e4lt. Eine Hashtable enth\u00e4lt in der Regel auch leere Buckets.<\/li>\n<\/ul>\n\n\n\n<p>Wann sollte ein bin\u00e4rer Suchbaum eingesetzt werden und wann eine Hashtable?<\/p>\n\n\n\n<p>M\u00f6chte man \u00fcber alle Elemente in Sortierreihenfolge itererieren oder Bereichssuchen durchf\u00fchren, eignet sich der bin\u00e4re Suchbaum. Sollen lediglich Elemente eingef\u00fcgt, gesucht und gel\u00f6scht werden, sollte die \u2013 bei diesen Operationen schnellere \u2013 Hashtable eingesetzt werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaere-suche-vs-binaerer-suchbaum\">Bin\u00e4re Suche vs. bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Und zu gu\u00adter Letzt (da oft danach gefragt wird): <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Ein bin\u00e4rer Suchbaum ist eine <em>Datenstruktur<\/em> wie in diesem Artikel beschrieben. <\/li>\n\n\n\n<li>Die <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaere-suche-java\/\">bin\u00e4re Suche<\/a> hingegen ist ein <em>Algorithmus<\/em>, mit der in einer sortierten Liste gesucht werden kann.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"fazit\">Fazit<\/h2>\n\n\n\n<p>Dieses Tutorial hat dir gezeigt, was ein bin\u00e4rer Suchbaum ist, und wie man in diesem schnell Elemente suchen, einf\u00fcgen und l\u00f6schen kann. Du hast beispielhafte Implementierungen in Java kennengelernt - eine rekursive und eine iterative. Und ich habe dir die Unterschiede des bin\u00e4ren Suchbaums gegen\u00fcber anderen Datenstrukturen aufgelistet.<\/p>\n\n\n\n<p>Im den n\u00e4chsten Teilen der Serie werde ich dir die konkreten BST-Implementierungen <a href=\"\/de\/algorithmen\/avl-baum-java\/\">AVL-Baum<\/a> und <a href=\"\/de\/algorithmen\/rot-schwarz-baum-java\/\">Rot-Schwarz-Baum<\/a> vorstellen.<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Was ist ein Bin\u00e4rer Suchbaum (BST)? Wie f\u00fcgt man neue Elemente ein, wie sucht man sie, und wie l\u00f6scht man sie wieder? Wie implementiert man den BST in Java? Und wie unterscheidet er sich von \u00e4hnlichen Datenstrukturen?<\/p>\n","protected":false},"author":1,"featured_media":30730,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Was ist ein bin\u00e4rer Suchbaum (BST)? Wie f\u00fcgt man Elemente ein, sucht, l\u00f6scht sie? Was unterscheidet den BST von \u00e4hnlichen Datenstrukturen?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":37969,"_post_count":0,"footnotes":""},"categories":[127],"tags":[174],"class_list":["post-21256","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-baeume"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/06\/binary-search-tree-1770x986-1.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Was ist ein Bin\u00e4rer Suchbaum (BST)? Wie f\u00fcgt man neue Elemente ein, wie sucht man sie, und wie l\u00f6scht man sie wieder? Wie implementiert man den BST in Java? Und wie unterscheidet er sich von \u00e4hnlichen Datenstrukturen?","public_identification_id":"66d14b30def343fc85443700c858a380","private_identification_id":"df857aaa2ebf4f32ac235fd9b9f877f2","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/21256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=21256"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/21256\/revisions"}],"predecessor-version":[{"id":52486,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/21256\/revisions\/52486"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/30730"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=21256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=21256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=21256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}