{"id":22179,"date":"2021-08-31T18:51:54","date_gmt":"2021-08-31T16:51:54","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=22179"},"modified":"2025-06-12T09:12:24","modified_gmt":"2025-06-12T07:12:24","slug":"avl-baum-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/avl-baum-java\/","title":{"rendered":"AVL-Baum (mit Java-Code)"},"content":{"rendered":"\n<p>Ein AVL-Baum ist eine konkrete Implementierung eines <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Balancierter_binarer_Suchbaum\">balancierten bin\u00e4ren Suchbaums<\/a>. Er wurde 1962 von den sowjetischen Informatikern Georgi Maximowitsch <strong>A<\/strong>delson-<strong>V<\/strong>elski und Jewgeni Michailowitsch <strong>L<\/strong>andis entwickelt und nach deren Initialen benannt.<\/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 AVL-Baum?<\/li>\n\n\n\n<li>Wie berechnet man den Balance-Faktor in einem AVL-Baum?<\/li>\n\n\n\n<li>Wie funktioniert eine AVL-Baum-Rotation?<\/li>\n\n\n\n<li>Wie f\u00fcgt man Elemente ein, und wie l\u00f6scht man sie?<\/li>\n\n\n\n<li><span style=\"color: initial;\">Wie implementiert man einen AVL-Baum in Java?<\/span><\/li>\n\n\n\n<li><span style=\"color: initial;\">Welche Zeitkomplexit\u00e4t haben die Operationen des AVL-Baums?<\/span><\/li>\n\n\n\n<li>Was unterscheidet den AVL-Baum vom Rot-Schwarz-Baum?<\/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=\"was-ist-ein-avl-baum\">Was ist ein AVL-Baum?<\/h2>\n\n\n\n<p>Ein AVL-Baum ist ein balancierter bin\u00e4rer Suchbaum \u2013 also ein <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/\">bin\u00e4rer Suchbaum<\/a>, in dem sich die H\u00f6hen der linken und rechten Teilb\u00e4ume eines jeden Knotens um maximal eins unterscheiden.<\/p>\n\n\n\n<p>Nach jeder Einf\u00fcge- und L\u00f6schoperation wird diese Eigenschaft \u00fcberpr\u00fcft und die Balance ggf. durch AVL-Rotation wiederhergestellt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"hoehe-eines-avl-baums\">H\u00f6he eines AVL-Baums<\/h3>\n\n\n\n<p>Die H\u00f6he eines (Teil-)baums gibt an, wie weit die Wurzel vom tiefsten Knoten entfernt ist. Ein (Teil-)Baum, der nur aus einem Wurzelknoten besteht, hat demnach die H\u00f6he 0.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"207\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-800x207.png\" alt=\"H\u00f6he eines AVL-Baums und seiner Teilb\u00e4ume\" class=\"wp-image-22193\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-800x207.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-224x58.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-336x87.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-504x130.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-672x174.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-400x104.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-600x155.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-944x244.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2-1200x311.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-node-height-v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">H\u00f6he eines AVL-Baums und seiner Teilb\u00e4ume<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"avl-baum-balance-faktor\">AVL-Baum Balance-Faktor<\/h3>\n\n\n\n<p>Der Balance-Faktor \"BF\" eines Knotens \"node\" bezeichnet die Differenz der H\u00f6hen \"H\" des rechten und linken Teilbaums (\"node.right\" und \"node.left\"):<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>BF(node) = H(node.right) - H(node.left)<\/em><\/p>\n\n\n\n<p>Die H\u00f6he eines nicht vorhandenen Teilbaums ist -1 (eins weniger als die H\u00f6he eines Teilbaums, der aus nur einem Knoten besteht).<\/p>\n\n\n\n<p>Man unterscheidet drei F\u00e4lle:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Bei einem Balance-Faktor von &lt; 0 spricht man von einem <em>linkslastigen<\/em> Knoten.<\/li>\n\n\n\n<li>Bei einem Balance-Faktor von > 0 spricht man von einem <em>rechtslastigen<\/em> Knoten.<\/li>\n\n\n\n<li>Ein Balance-Faktor von 0 steht f\u00fcr einen <em>h\u00f6hengleichen oder ausgewogenen<\/em> Knoten.<\/li>\n<\/ul>\n\n\n\n<p>In einem AVL-Baum ist der Balance-Faktor an jedem Knoten -1, 0 oder 1.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"avl-baum-beispiel\">AVL-Baum-Beispiel<\/h3>\n\n\n\n<p>Das folgende Beispiel zeigt einen AVL-Baum mit Angabe von H\u00f6he und Balance-Faktor an jedem Knoten:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"291\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-600x291.png\" alt=\"Beispiel-AVL-Baum mit Angabe von H\u00f6he und Balance-Faktor\" class=\"wp-image-22198\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-600x291.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-224x109.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-504x244.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-672x326.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-800x388.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example-944x458.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-example.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Beispiel-AVL-Baum mit Angabe von H\u00f6he und Balance-Faktor<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Knoten 2 und 7 sind in diesem Beispiel rechtslastig, Knoten 4 ist linkslastig. Alle anderen Knoten sind ausgewogen.<\/p>\n\n\n\n<p>Der folgende Baum hingegen ist <em>kein<\/em> AVL-Baum, da das AVL-Kriterum (<em>-1 \u2264 BF \u2264 1<\/em>) an Knoten 4 nicht erf\u00fcllt ist. Dessen linker Teilbaum hat die H\u00f6he 1 und der rechte, leere Teilbaum die H\u00f6he -1. Die Differenz daraus ist -2.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"291\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-600x291.png\" alt=\"Bin\u00e4rer Suchbaum, der das AVL-Kriterium nicht erf\u00fcllt\" class=\"wp-image-22202\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-600x291.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-224x109.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-504x244.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-672x326.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-800x388.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example-944x458.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-unbalanced-example.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rer Suchbaum, der das AVL-Kriterium nicht erf\u00fcllt<\/figcaption><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"implementierung-eines-avl-baums-in-java\">Implementierung eines AVL-Baums in Java<\/h2>\n\n\n\n<p>Als Basis f\u00fcr die Implementierung des AVL-Baums in Java verwenden wir den <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Binarer_Suchbaum_in_Java\">Java-Quellcode f\u00fcr den bin\u00e4ren Suchbaum<\/a> aus dem vorangegangenen Tutorial der Bin\u00e4rbaum-Serie.<\/p>\n\n\n\n<p>Knoten werden durch die Klasse <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/Node.java\" target=\"_blank\">Node<\/a><\/code> dargestellt. F\u00fcr den Knotenwert <code>data<\/code> verwenden wir der Einfachheit halber <code>int<\/code>-Primitive. In <code>height<\/code> speichern wir die H\u00f6he des Teilbaums, dessen Wurzel dieser Knoten darstellt.<\/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-keyword\">int<\/span> height;\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> data)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.data = data;\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>Der AVL-Baum wird durch die Klasse <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/AvlTree.java\" target=\"_blank\">AvlTree<\/a><\/code> implementiert. Diese erweitert die im vorangegenen Teil vorgestellte Klasse <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java\" target=\"_blank\">BinarySearchTreeRecursive<\/a><\/code>. Wir werden einen Gro\u00dfteil deren Funktionalit\u00e4t wiederverwenden.<\/p>\n\n\n\n<p>F\u00fcr die Balancierung des AVL-Baums ben\u00f6tigen wir folgende drei zus\u00e4tzliche Methoden:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>height()<\/code> liefert die in <code>node.height<\/code> hinterlegte H\u00f6he eines Teilbaums \u2012 oder -1 f\u00fcr einen leeren Teilbaum.<\/li>\n\n\n\n<li><code>updateHeight()<\/code> setzt <code>node.height<\/code> als maximale H\u00f6he der Kinder plus 1.<\/li>\n\n\n\n<li><code>balanceFactor()<\/code> berechnet den Balance-Faktor eines Knotens.<\/li>\n<\/ul>\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\">class<\/span> <span class=\"hljs-title\">AvlTree<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">BinarySearchTreeRecursive<\/span> <\/span>{\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">height<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> node != <span class=\"hljs-keyword\">null<\/span> ? node.height : -<span class=\"hljs-number\">1<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">updateHeight<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> leftChildHeight = height(node.left);\n    <span class=\"hljs-keyword\">int<\/span> rightChildHeight = height(node.right);\n    node.height = max(leftChildHeight, rightChildHeight) + <span class=\"hljs-number\">1<\/span>;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">balanceFactor<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> height(node.right) <span class=\"hljs-function\">- <span class=\"hljs-title\">height<\/span><span class=\"hljs-params\">(node.left)<\/span><\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ ...<\/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>Der Code wird in den folgenden Abschnitten Schritt f\u00fcr Schritt erweitert.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"avl-baum-rotation\">AVL-Baum Rotation<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Einfugen_im_binaren_Suchbaum\">Einf\u00fcgen<\/a> in und <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Loschen_im_binaren_Suchbaum\">L\u00f6schen<\/a> aus einem AVL-Baum funktioniert grunds\u00e4tzlich so wie im Artikel \u00fcber bin\u00e4re Suchb\u00e4ume beschrieben.<\/p>\n\n\n\n<p>Wenn nach einer Einf\u00fcge- oder L\u00f6schoperation das AVL-Kriterium nicht mehr erf\u00fcllt ist, muss der Baum rebalanciert werden. Dies geschieht durch sogenannte Rotationen. <\/p>\n\n\n\n<p>Man unterscheidet zwischen Rechts- und Links-Rotation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rechts-rotation\">Rechts-Rotation<\/h3>\n\n\n\n<p>Die folgende Grafik zeigt eine Rechts-Rotation. Der dargestellte (Teil-)baum enth\u00e4lt folgende Knoten:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>N<\/em>: der Knoten, an dem ein Ungleichgewicht festgestellt wurde<\/li>\n\n\n\n<li><em>L<\/em>: der linke Kind-Knoten von <em>N<\/em><\/li>\n\n\n\n<li><em>LL<\/em>: der linke Kind-Knoten von <em>L<\/em><\/li>\n\n\n\n<li><em>LR<\/em>: der rechte Kind-Knoten von <em>L<\/em><\/li>\n\n\n\n<li><em>R<\/em>: der rechte Kind-Knoten von <em>N<\/em><\/li>\n<\/ul>\n\n\n\n<p>Unter den Buchstaben wird jeweils in Klammern ein beispielhafter Knoten-Wert angezeigt. An diesem ist gut zu erkennen, dass vor der Rotation folgende In-Order-Reihenfolge gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>LL (1) &lt; L (2) &lt; LR (3) &lt; N (4) &lt; R (5)<\/em><\/p>\n\n\n\n<p>W\u00e4hrend der Rotation wandert Knoten <em>L<\/em> an die Wurzel, und die vorherige Wurzel <em>N<\/em> wird zum rechten Kind von <em>L<\/em>. Das vorherige rechte Kind von <em>L<\/em>, <em>LR<\/em> wird zum neuen linken Kind von <em>N<\/em>. Die zwei restlichen Knoten, <em>LL<\/em> und <em>R<\/em> bleiben unver\u00e4ndert relativ zu ihrem Elternknoten.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-800x228.png\" alt=\"Rechts-Rotation im AVL-Baum\" class=\"wp-image-22207\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-right-rotation.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Rechts-Rotation im AVL-Baum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>An den Beispiel-Werten in Klammern sieht man gut, dass sich durch die Rotation die In-Order-Reihenfolge der Knoten nicht ver\u00e4ndert hat.<\/p>\n\n\n\n<p>Der Java-Code f\u00fcr die Rechts-Rotation ist unkompliziert (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/AvlTree.java#L71\" target=\"_blank\">Klasse <code>AvlTree<\/code>, ab Zeile 71<\/a>).<\/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-function\"><span class=\"hljs-keyword\">private<\/span> Node <span class=\"hljs-title\">rotateRight<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node leftChild = node.left;\n\n  node.left = leftChild.right;\n  leftChild.right = node;\n\n  updateHeight(node);\n  updateHeight(leftChild);\n\n  <span class=\"hljs-keyword\">return<\/span> leftChild;\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>Wir merken uns das linke Kind <code>leftChild<\/code> (in der Grafik <em>L<\/em>) von <code>node<\/code> (in der Grafik <em>N<\/em>), ersetzen das linke Kind von <code>node<\/code> durch das rechte Kind des linken Kindes <code>leftChild.right<\/code> (in der Grafik <em>LR<\/em>) und setzen dann <code>node<\/code> als neues rechtes Kind des linken Kindes.<\/p>\n\n\n\n<p>Danach aktualisieren wir die H\u00f6hen der Teilb\u00e4ume in der gezeigten Reihenfolge. Die <code>updateHeight()<\/code>-Methode habe ich bereits im Abschnitt <a href=\"#Implementierung_eines_AVL-Baums_in_Java\">Implementierung eines AVL-Baums in Java<\/a> vorgestellt.<\/p>\n\n\n\n<p>R\u00fcckgabewert ist der neue Wurzelknoten <code>leftChild<\/code> (in der Grafik <em>L<\/em>).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"links-rotation\">Links-Rotation<\/h3>\n\n\n\n<p>Die Links-Rotation funktioniert analog:<\/p>\n\n\n\n<p>Knoten <em>R<\/em> wird zur Wurzel; die vorherige Wurzel <em>N<\/em> wird zum linken Kind von <em>R<\/em>. Das vorherige linke Kind von <em>R<\/em>, <em>RL<\/em> wird zum neuen rechten Kind von <em>N<\/em>. Die relativen Positionen der Knoten <em>RR<\/em> und <em>L<\/em> \u00e4ndern sich nicht.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-800x228.png\" alt=\"Links-Rotation im AVL-Baum\" class=\"wp-image-22228\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-left-rotation-v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Links-Rotation im AVL-Baum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Auch bei der Links-Rotation bleibt die In-Order-Reihenfolge der Knoten (<em>L &lt; N &lt; RL &lt; R &lt; RR<\/em>) erhalten.<\/p>\n\n\n\n<p>Der Java-Code sieht wie folgt aus (<a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/AvlTree.java#L83\" target=\"_blank\" rel=\"noopener\">Klasse <code>AvlTree<\/code>, ab Zeile 83<\/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\">private<\/span> Node <span class=\"hljs-title\">rotateLeft<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node rightChild = node.right;\n\n  node.right = rightChild.left;\n  rightChild.left = node;\n\n  updateHeight(node);\n  updateHeight(rightChild);\n\n  <span class=\"hljs-keyword\">return<\/span> rightChild;\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<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"avl-baum-balancieren\">AVL-Baum balancieren<\/h2>\n\n\n\n<p>Nach dem Einf\u00fcgen in oder L\u00f6schen aus dem AVL-Baum berechnen wir die H\u00f6he und den Balance-Faktor vom eingef\u00fcgten oder gel\u00f6schten Knoten aus aufw\u00e4rts bis zur Wurzel.<\/p>\n\n\n\n<p>Wenn wir an einem Knoten feststellen, dass das AVL-Kriterium nicht mehr erf\u00fcllt ist (der Balance-Faktor also kleiner als -1 oder gr\u00f6\u00dfer als +1 ist), m\u00fcssen wir rebalancieren. Dabei unterscheiden wir vier F\u00e4lle:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Linkslastigen Knoten ausgleichen:\n<ul class=\"wp-block-list\">\n<li>Rechts-Rotation<\/li>\n\n\n\n<li>Links-Rechts-Rotation<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Rechtslastigen Knoten ausgleichen:\n<ul class=\"wp-block-list\">\n<li>Links-Rotation<\/li>\n\n\n\n<li>Rechts-Links-Rotation<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>Im folgenden beschreibe ich die vier F\u00e4lle an verschiedenen Beispielen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rebalancieren-durch-rechts-rotation\">Rebalancieren durch Rechts-Rotation<\/h3>\n\n\n\n<p>Wir f\u00fcgen in einen leeren Baum die Knoten 3, 2 und 1 ein. Ohne Rebalancierung sieht der Baum dann wie folgt aus:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-400x229.png\" alt=\"Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 3, 2, 1\" class=\"wp-image-22236\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-336x192.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-right-rotation-necessary.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 3, 2, 1<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir pr\u00fcfen den Balance-Faktor vom zuletzt eingef\u00fcgten Knoten 1 aus aufw\u00e4rts:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Der Balance-Faktor an Knoten 1 betr\u00e4gt 0.<\/li>\n\n\n\n<li>Der Balance-Faktor an Knoten 2 betr\u00e4gt -1; Knoten 2 ist also linkslastig. Das AVL-Kriterium (<em>-1 \u2264 BF \u2264 1<\/em>) ist aber noch erf\u00fcllt.<\/li>\n\n\n\n<li>Der Balance-Faktor an Knoten 3 betr\u00e4gt -2; hier ist das AVL-Kriterium nicht mehr erf\u00fcllt.<\/li>\n<\/ul>\n\n\n\n<p>In diesem Fall m\u00fcssen wir eine Rechts-Rotation um Knoten 3 ausf\u00fchren:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-600x229.png\" alt=\"Rebalancierung des AVL-Baums durch Rechts-Rotation\" class=\"wp-image-31775\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-600x229.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-224x85.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-336x128.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-504x192.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-672x256.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-400x153.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-800x305.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2-944x360.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-rotation.v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Rebalancierung des AVL-Baums durch Rechts-Rotation<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die neue Wurzel ist Knoten 2, und dessen Balance-Faktor ist 0. Der AVL-Baum ist wieder balanciert.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rebalancieren-durch-links-rechts-rotation\">Rebalancieren durch Links-Rechts-Rotation<\/h3>\n\n\n\n<p>In folgendem Beispiel haben wir ebenfalls eine linkslastige Wurzel, allerdings sieht die Situation etwas anders aus. Dieses mal f\u00fcgen wir die Knoten in der Reihenfolge 3, 1, 2 ein:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-400x229.png\" alt=\"Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 3, 1, 2\" class=\"wp-image-22241\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-336x192.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-balancing-left-right-rotation-necessary.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 3, 1, 2<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir stellen fest, dass an der Wurzel (mit einem Balance-Faktor von -2) das AVL-Kriterium nicht erf\u00fcllt ist. W\u00fcrden wir jetzt \u2013 wie im vorangegangenen Beispiel \u2013 eine Rechts-Rotation ausf\u00fchren, s\u00e4he der Baum danach wie folgt aus:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-600x229.png\" alt=\"AVL-Baum ist nach Rechts-Rotation nicht balanciert\" class=\"wp-image-31777\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-600x229.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-224x85.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-336x128.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-504x192.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-672x256.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-400x153.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-800x305.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3-944x360.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-right-rotation.v3.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">AVL-Baum ist nach Rechts-Rotation nicht balanciert<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Das rechte Kind der 1 \u2013 die 2 \u2013 wurde zum linken Kind der 3. Anstatt einer linkslastigen Wurzel mit BF -2 haben wir nun eine rechtslastige Wurzel mit BF +2. Wir sind am Ziel vorbeigeschossen.<\/p>\n\n\n\n<p>Was k\u00f6nnen wir stattdessen tun?<\/p>\n\n\n\n<p>Die korrekte Vorgehensweise f\u00fcr diesen Fall (linkes Kind der Wurzel ist rechtslastig) ist eine sogenannte Links-Rechts-Rotation. Zuerst rotieren wir nach links um Knoten 1 und danach nach rechts um Knoten 3:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"230\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-800x230.png\" alt=\"Rebalancierung des AVL-Baums durch Links-Rechts-Rotation\" class=\"wp-image-31782\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-800x230.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-336x97.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-504x145.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-672x193.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-600x173.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-944x271.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2-1200x345.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-right-rotation.v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Rebalancierung des AVL-Baums durch Links-Rechts-Rotation<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Mit einem Balance-Faktor von 0 an der neuen Wurzel 2 ist der AVL-Baum wieder balanciert. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rebalancieren-durch-links-rotation\">Rebalancieren durch Links-Rotation<\/h3>\n\n\n\n<p>F\u00fcr rechtslastige Knoten gehen wir analog vor. Wir f\u00fcgen zun\u00e4chst Knoten in der Reihenfolge 1, 2, 3 ein und erhalten den folgenden unbalancierten Baum:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-400x229.png\" alt=\"Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 1, 2, 3\" class=\"wp-image-31784\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-336x192.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation-necessary.v3.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 1, 2, 3<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Der Balance-Faktor an der Wurzel betr\u00e4gt +2. Wir k\u00f6nnen die Balance durch einfache Links-Rotation wiederherstellen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-600x229.png\" alt=\"Rebalancierung des AVL-Baums durch Links-Rotation\" class=\"wp-image-31786\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-600x229.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-224x85.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-336x128.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-504x192.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-672x256.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-400x153.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-800x305.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2-944x360.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-left-rotation.v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Rebalancierung des AVL-Baums durch Links-Rotation<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rebalancieren-durch-rechts-links-rotation\">Rebalancieren durch Rechts-Links-Rotation<\/h3>\n\n\n\n<p>Das vierte und letzte Beispiel zeigt einen AVL-Baum, in den die Knoten in der Reihenfolge 1, 3, 2 eingef\u00fcgt wurden:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"230\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-400x230.png\" alt=\"Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 1, 3, 2\" class=\"wp-image-31788\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-400x230.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-224x129.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-336x193.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-504x290.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-672x386.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2-600x345.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation-necessary.v2.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Unbalancierter AVL-Baum nach dem Einf\u00fcgen von 1, 3, 2<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Der Balance-Faktor an der Wurzel betr\u00e4gt auch hier +2. Doch bei einer Links-Rotation wie im vorangegangenen Beispiel w\u00fcrde folgendes passieren:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"230\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-600x230.png\" alt=\"AVL-Baum ist nach Links-Rotation nicht balanciert\" class=\"wp-image-31790\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-600x230.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-224x86.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-336x129.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-504x193.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-672x258.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-400x153.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-800x307.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2-944x362.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-not-balanced-after-left-rotation.v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">AVL-Baum ist nach Links-Rotation nicht balanciert<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Das linke Kind der 3 \u2013 die 2 \u2013 wurde zum rechten Kind der 1. Statt einer rechtslastigen haben wir jetzt eine linkslastige Wurzel mit dem Balance-Faktor -2.<\/p>\n\n\n\n<p>Analog zum zweiten Fall ist die korrekte Vorgehensweise in diesem Fall (rechts Kind der Wurzel ist linkslastig) eine Rechts-Links-Rotation. Wir rotieren nach rechts um Knoten 3 und dann nach links um Knoten 1:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"230\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-800x230.png\" alt=\"Rebalancierung des AVL-Baums durch Rechts-Links-Rotation\" class=\"wp-image-31792\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-800x230.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-336x97.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-504x145.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-672x193.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-600x173.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-944x271.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2-1200x345.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/06\/avl-tree-balancing-right-left-rotation.v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Rebalancierung des AVL-Baums durch Rechts-Links-Rotation<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Damit hast du alle Varianten der Balancierung des AVL-Baums kennengelernt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"java-code-fuer-die-rebalancierung\">Java-Code f\u00fcr die Rebalancierung<\/h3>\n\n\n\n<p>Die vier vorangegangenen Abschnitte zusammengefasst ergeben folgende Rebalancierungs-Vorschrift. <em>BF<\/em> steht dabei f\u00fcr Balance-Funktion, <em>N<\/em> f\u00fcr den betrachteten Knoten, und <em>L<\/em> und <em>R<\/em> f\u00fcr dessen linkes bzw. rechtes Kind.<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-left\" data-align=\"left\">Fall<\/th><th class=\"has-text-align-left\" data-align=\"left\">Bedingung<\/th><th>Rebalancierung<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">1.<\/td><td class=\"has-text-align-left\" data-align=\"left\"><em>BF(N)<\/em> &lt; -1 und <em>BF(L)<\/em> \u2264 0<\/td><td>Rechts-Rotation um <em>N<\/em><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">2.<\/td><td class=\"has-text-align-left\" data-align=\"left\"><em>BF(N)<\/em> &lt; -1 und <em>BF(L)<\/em> &gt; 0<\/td><td>Links-Rotation um <em>L<\/em> gefolgt von Rechts-Rotation um <em>N<\/em><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">3.<\/td><td class=\"has-text-align-left\" data-align=\"left\"><em>BF(N)<\/em> &gt; 1 und <em>BF(R)<\/em> \u2265 0 <\/td><td>Links-Rotation um <em>N<\/em><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">4.<\/td><td class=\"has-text-align-left\" data-align=\"left\"><em>BF(N)<\/em> &gt; 1 und <em>BF(R)<\/em> &lt; 0<\/td><td>Rechts-Rotation um <em>R<\/em> gefolgt von Links-Rotation um <em>N<\/em><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Im Java-Code implementieren wir den Rebalancierungs-Algorithmus in der folgenden <code>rebalance()<\/code>-Methode (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/AvlTree.java#L41\" target=\"_blank\">Klasse <code>AvlTree<\/code>, ab Zeile 41<\/a>):<\/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\">private<\/span> Node <span class=\"hljs-title\">rebalance<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> balanceFactor = balanceFactor(node);\n\n  <span class=\"hljs-comment\">\/\/ Left-heavy?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (balanceFactor &lt; -<span class=\"hljs-number\">1<\/span>) {\n    <span class=\"hljs-keyword\">if<\/span> (balanceFactor(node.left) &lt;= <span class=\"hljs-number\">0<\/span>) {    <span class=\"hljs-comment\">\/\/ Case 1<\/span>\n      <span class=\"hljs-comment\">\/\/ Rotate right<\/span>\n      node = rotateRight(node);\n    } <span class=\"hljs-keyword\">else<\/span> {                                <span class=\"hljs-comment\">\/\/ Case 2<\/span>\n      <span class=\"hljs-comment\">\/\/ Rotate left-right<\/span>\n      node.left = rotateLeft(node.left);\n      node = rotateRight(node);\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Right-heavy?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (balanceFactor &gt; <span class=\"hljs-number\">1<\/span>) {\n    <span class=\"hljs-keyword\">if<\/span> (balanceFactor(node.right) &gt;= <span class=\"hljs-number\">0<\/span>) {    <span class=\"hljs-comment\">\/\/ Case 3<\/span>\n      <span class=\"hljs-comment\">\/\/ Rotate left<\/span>\n      node = rotateLeft(node);\n    } <span class=\"hljs-keyword\">else<\/span> {                                 <span class=\"hljs-comment\">\/\/ Case 4<\/span>\n      <span class=\"hljs-comment\">\/\/ Rotate right-left<\/span>\n      node.right = rotateRight(node.right);\n      node = rotateLeft(node);\n    }\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> node;\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<p>Der Code entspricht dem oben beschriebenen Algorithmus; die vier F\u00e4lle sind jeweils als Kommentar im Code referenziert. Die Methode liefert den neuen Wurzelknoten des (Teil-)baums zur\u00fcck.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"operationen-im-avl-baum\">Operationen im AVL-Baum<\/h2>\n\n\n\n<p>Da wir nun das Werkzeug f\u00fcr die Rebalancierung des Baums haben (die <code>rebalance()<\/code>-Methode aus dem vorherigen Abschnitt), k\u00f6nnen wir die Methoden zum Einf\u00fcgen und L\u00f6schen zusammenbauen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"einfuegen-in-einen-avl-baum\">Einf\u00fcgen in einen AVL-Baum<\/h3>\n\n\n\n<p>Um einen Knoten in den AVL-Baum einzuf\u00fcgen, gehen wir zun\u00e4chst so vor, wie im <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Einfugen_im_binaren_Suchbaum\">Abschnitt \"Einf\u00fcgen im bin\u00e4ren Suchbaum\" des vorangegangenen Tutorials<\/a> beschrieben. Im Anschluss rufen wir <code>updateHeight()<\/code> und <code>rebalance()<\/code> auf.<\/p>\n\n\n\n<p>Da unsere <code>AvlTree<\/code>-Klasse von <code>BinarySearchTreeRecursive<\/code> erbt, erfolgt der Aufruf der Einf\u00fcge-Methode \u00fcber <code>super.insertNode()<\/code> (definiert in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L34\" target=\"_blank\" rel=\"noreferrer noopener\"><code>BinarySearchTreeRecursive<\/code> ab Zeile 34<\/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-meta\">@Override<\/span>\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  node = <span class=\"hljs-keyword\">super<\/span>.insertNode(key, node);\n\n  updateHeight(node);\n\n  <span class=\"hljs-keyword\">return<\/span> rebalance(node);\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<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"loeschen-aus-einem-avl-baum\">L\u00f6schen aus einem AVL-Baum<\/h3>\n\n\n\n<p>Zum L\u00f6schen eines Knotens gehen wir vor wie im <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/#Loschen_im_binaren_Suchbaum\">Abschnitt \"L\u00f6schen im bin\u00e4ren Suchbaum\" des vorangegangenen Tutorials<\/a> beschrieben. Im Anschluss rufen wir \u2013 wie beim Einf\u00fcgen \u2013 <code>updateHeight()<\/code> und <code>rebalance()<\/code> auf:<\/p>\n\n\n\n<p>Die mit <code>super.deleteNode()<\/code> aufgerufene Methode findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L57\" target=\"_blank\"><code>BinarySearchTreeRecursive<\/code> ab Zeile 57<\/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-meta\">@Override<\/span>\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  node = <span class=\"hljs-keyword\">super<\/span>.deleteNode(key, node);\n\n  <span class=\"hljs-comment\">\/\/ Node is null if the tree doesn't contain the key<\/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  updateHeight(node);\n\n  <span class=\"hljs-keyword\">return<\/span> rebalance(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<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"navigation-im-avl-baum\">Navigation im AVL-Baum<\/h3>\n\n\n\n<p>Die Suche im AVL-Baum funktioniert exakt wie die <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Suche_im_binaren_Suchbaum\">Suche im bin\u00e4ren Suchbaum<\/a>. Die <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L10\" target=\"_blank\" rel=\"noopener\"><code>searchNode()<\/code>-Methode aus <code>BinarySearchTreeRecursive<\/code><\/a> muss daher nicht \u00fcberschrieben werden.<\/p>\n\n\n\n<p>Die Traversierung in Pre-order-, Post-order-, In-order-, Reverse-in-order- und Level-order-Reihenfolge wird f\u00fcr Bin\u00e4rb\u00e4ume im Allgemeinen definiert. Du findest die Definitionen im <a href=\"\/de\/algorithmen\/binaerbaum-java\/#Binarbaum-Traversierung\">Abschnitt \"Bin\u00e4rbaum-Traversierung\" des Artikels \u00fcber Bin\u00e4rb\u00e4ume<\/a>.<\/p>\n\n\n\n<p>Die in dem Artikel vorgestellten Traversierungsklassen <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversal.java\" target=\"_blank\">DepthFirstTraversal<\/a><\/code>, <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java\" target=\"_blank\">DepthFirstTraversalIterative<\/a><\/code> und <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java\" target=\"_blank\">DepthFirstTraversalRecursive<\/a><\/code> k\u00f6nnen auch auf den <code>AvlTree<\/code> angewendet werden, da dieser indirekt das Interface&nbsp;<code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinaryTree.java\" target=\"_blank\">BinaryTree<\/a><\/code> implementiert, auf dem die Traversierungsfunktionen definiert sind.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-des-avl-baums\">Zeitkomplexit\u00e4t des AVL-Baums<\/h2>\n\n\n\n<p>(Eine Erkl\u00e4rung der Zeitkomplexit\u00e4t und von Komplexit\u00e4tsklassen wie <em>O(log n)<\/em> findest du im Artikel \"<a href=\"\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt<\/a>\".)<\/p>\n\n\n\n<p>Beim Suchen, Einf\u00fcgen und L\u00f6schen fallen folgende Operationen an:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die maximale Anzahl an Knoten-Vergleichsoperationen entspricht der H\u00f6he des AVL-Baumes.<\/li>\n\n\n\n<li>Die maximale Anzahl an Berechnungen des Balance-Faktors ist doppelt so hoch, da auch immer der Balance-Faktor eines Kindes mit ber\u00fccksichtigt werden muss.<\/li>\n\n\n\n<li>Die maximale Anzahl an Rotationen entspricht ebenfalls der doppelten H\u00f6he des AVL-Baumes, da pro Ebene keine, eine oder zwei Rotationen durchgef\u00fchrt werden.<\/li>\n\n\n\n<li>Pro Rotation wird f\u00fcr zwei Knoten die H\u00f6he neu berechnet. Die maximale Anzahl an H\u00f6hen-Berechnungen betr\u00e4gt also das Vierfache der Baumh\u00f6he.<\/li>\n<\/ul>\n\n\n\n<p>Da es sich bei einem AVL-Baum um einen balancierten Bin\u00e4rbaum handelt \u2013 bei Verdoppelung der Knotenzahl also lediglich eine Ebene hinzukommt \u2013 liegt die H\u00f6he des AVL-Baumes in der Gr\u00f6\u00dfenordnung <em>O(log n)<\/em>.<\/p>\n\n\n\n<p>Da die Kosten aller oben genannten Operationen konstant sind und die Anzahl ihrer Ausf\u00fchrungen jeweils proportional zur Baumh\u00f6he ist, betr\u00e4gt auch die Zeitkomplexit\u00e4t f\u00fcr das Suchen, Einf\u00fcgen und L\u00f6schen jeweils <em>O(log 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=\"avl-baum-im-vergleich-mit-anderen-datenstrukturen\">AVL-Baum im Vergleich mit anderen Datenstrukturen<\/h2>\n\n\n\n<p>In den folgenden Abschnitten findest du die Vor- und Nachteile des AVL-Baums gegen\u00fcber vergleichbaren Datenstrukturen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"avl-baum-vs-rot-schwarz-baum\">AVL-Baum vs. Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Sowohl der AVL-Baum als auch der <a href=\"\/de\/algorithmen\/rot-schwarz-baum-java\/\">Rot-Schwarz-Baum<\/a> sind selbst-balancierende bin\u00e4re Suchb\u00e4ume.<\/p>\n\n\n\n<p>Beim AVL-Baum erfolgt die Rebalancierung durch Berechnung von Balance-Faktoren und nachfolgenden Rotationen. Die absolute H\u00f6hendifferenz ist an keinem Knoten gr\u00f6\u00dfer als 1.<\/p>\n\n\n\n<p>Im Rot-Schwarz-Baum werden die Knoten durch Farben (rot \/ schwarz) gekennzeichnet. Rotationen erfolgen, wenn bestimmte Kriterien f\u00fcr Farbfolgen nicht mehr eingehalten sind. Die absolute H\u00f6hendifferenz an einem Knoten kann auch gr\u00f6\u00dfer als 1 sein. Genauer gesagt: das tiefste Blatt kann von der Wurzel bis zu doppelt so weit entfernt sein wie das h\u00f6chste Blatt.<\/p>\n\n\n\n<p>Diese Eigenschaften f\u00fchren zu folgenden Unterschieden:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die Suche im AVL-Baum ist in der Regel schneller als im Rot-Schwarz-Baum, da der AVL-Baum besser balanciert ist.<\/li>\n\n\n\n<li>Das Einf\u00fcgen und L\u00f6schen ist hingegen im Rot-Schwarz-Baum schneller, da dieser seltener rebalanciert wird.<\/li>\n\n\n\n<li>AVL-B\u00e4ume ben\u00f6tigen ein Extra-Byte pro Knoten f\u00fcr das Speichern der jeweiligen H\u00f6he. Rot-Schwarz-B\u00e4ume ben\u00f6tigen lediglich ein Bit pro Knoten f\u00fcr die Farb-Information. In der Java-Praxis macht dies keinen Unterschied, da f\u00fcr das Bit mindestens ein Byte belegt wird.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"avl-baum-vs-binaerer-suchbaum\">AVL-Baum vs. Bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Ein AVL-Baum ist ein bin\u00e4rer Suchbaum, der nach jeder Einf\u00fcge- und L\u00f6sch-Operation durch Rotation das AVL-Kriterium wiederherstellt.<\/p>\n\n\n\n<p>Ein bin\u00e4rer Suchbaum muss nicht zwingend balanciert sein. Ebenso kann die Balancierung durch andere Algorithmen als beim AVL-Baum erreicht werden.<\/p>\n\n\n\n<p>Jeder AVL-Baum ist also ein bin\u00e4rer Suchbaum. Aber nicht jeder bin\u00e4re Suchbaum ist ein AVL-Baum.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"fazit\">Fazit<\/h2>\n\n\n\n<p>In diesem Tutorial hast du erfahren, was ein AVL-Baum ist und wie dieser nach Einf\u00fcge- oder L\u00f6schoperationen durch Einfach- oder Doppelrotation rebalanciert wird. Au\u00dferdem hast du gelernt, wie man einen AVL-Baum in Java implementiert.<\/p>\n\n\n\n<p>Im n\u00e4chsten Teil wird es um eine weitere konkrete Art des bin\u00e4ren Suchbaums gehen: den <a href=\"\/de\/algorithmen\/rot-schwarz-baum-java\/\">Rot-Schwarz-Baum<\/a>.<\/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 AVL-Baum? Wie berechnet man den Balance-Faktor eines Knotens? Wie funktioniert die Rotation und wie wird ein AVL-Baum balanciert? Wie implementiert man einen AVL-Baum in Java?<\/p>\n","protected":false},"author":1,"featured_media":30732,"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 AVL-Baum? Wie berechnet man den Balance-Faktor (BF)? Wie funktioniert AVL-Rotation? Wie wird ein AVL-Baum (re-)balanciert?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":17655,"_post_count":0,"footnotes":""},"categories":[127],"tags":[174],"class_list":["post-22179","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\/08\/avl-tree-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-tree-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/08\/avl-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":3,"uagb_excerpt":"Was ist ein AVL-Baum? Wie berechnet man den Balance-Faktor eines Knotens? Wie funktioniert die Rotation und wie wird ein AVL-Baum balanciert? Wie implementiert man einen AVL-Baum in Java?","public_identification_id":"6236670cd42e4671911beee624779a5a","private_identification_id":"4c043ae34f10465c8d8b631e72c379d1","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/22179","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=22179"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/22179\/revisions"}],"predecessor-version":[{"id":52487,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/22179\/revisions\/52487"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/30732"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=22179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=22179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=22179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}