AVL-Baum

[griNN3]

Hallo,

ich habe ein AVL-Baum-Programm geschrieben und bin es anschließend Schritt für Schritt durchgegangen. Im markierten Bereich ist mir dabei folgender Fehler aufgefallen:
Die Höhe des linken Teilbaums des Knotens 10 müsste den Wert 2 haben. Es wird jedoch angezeigt, dass die Höhe 3 beträgt, woraus sich für den Knoten 10 eine Balance von 2 ergibt. Wenn man diesen Teilbaum mittels der Informationen die im roten Bereich markiert sind ausgibt, fällt jedoch auf, dass der Knoten die Balance 1 haben muss.
Ich bin den Quelltext jetzt schon mehr als eine Stunde durchgegangen, aber finde einfach den Fehler nicht. Die Methoden height() und getBalance() scheinen korrekt zu sein.

public class AVLMain {

    public static void main(String[] args) {
        AVLTreeI avl = new AVLTreeI();

        avl.insert(20);
        avl.insert(10);
        avl.insert(5);
        avl.insert(7);
        avl.insert(8);
        avl.insert(9);
        avl.insert(15);
        avl.insert(30);
        avl.insert(13);
        System.out.println("postorder:");
        avl.printPostorder();
   
    }
}

public class AVLTree {

     private AVLTreeNode root;
    private int numberElements = 0;
   
    public void insert(Comparable elem) {
        if (root == null) {
            root = new AVLTreeNode(elem);
        } else {
            root = insertR(root, elem);
        }
        numberElements++;
    }

    private AVLTreeNode insertR(AVLTreeNode node, Comparable elem) {
        if (elem.compareTo(node.getElement()) < 0) {// left subtree
            if (node.getLeft() == null) {// no subtree –insert node
                node.setLeft(new AVLTreeNode(elem));
            } else {// insert in right subtree
                node.setLeft(insertR(node.getLeft(), elem));
                if(node.getElement().compareTo(10) == 0 && node.getLeft().getElement().compareTo(7)==0) {
                System.out.println("linker Nachfolger von "+node.getElement()+": "+node.getLeft().getElement());
                System.out.println("linker Nachfolger von: "+node.getLeft().getElement()+": "+node.getLeft().getLeft().getElement());
                System.out.println("rechter Nachfolger von: "+ node.getLeft().getElement()+": "+node.getLeft().getRight().getElement());
                System.out.println("rechter Nachfolger von: "+node.getElement()+ ": "+node.getRight().getElement());
                }
            }
        } else if (elem.compareTo(node.getElement()) == 0) {// nothing to do

        } else {
            // i > t.val
            // right subtree analogue left subtree

            if (node.getRight() == null) {// no subtree –insert node
                node.setRight(new AVLTreeNode(elem));
            } else {// insert in right subtree
                node.setRight(insertR(node.getRight(), elem));

            }
        }      
        System.out.println("balance von "+ node.getElement() +": "+node.getBalance());
       
        //AVL-Eigenschaft verletzt und es wurde im rechten Teilbaum des linken Kindes eingefügt
        if(node.getBalance()<1 && node.getRight()!=null && node.getRight().getBalance()>0) {
            System.out.println("fall 1");
            node.setRight(rotateRight(node.getRight()));
            return rotateLeft(node);
        }
       
        //AVL-Eigenschaft verletzt und es wurde im rechten Teilbaum des rechten Kindes eingefügt
        if(node.getBalance()<1 && node.getRight()!=null && node.getRight().getBalance()<0) {
            System.out.println("fall 2");
            return rotateLeft(node);
        }
       
        //AVL-Eigenschaft verletzt und es wurde im linken Teilbaum des rechten Kindes eingefügt
        if(node.getBalance()>1 && node.getLeft()!=null && node.getLeft().getBalance()<0) {
            System.out.println("fall 3");
            node.setLeft(rotateLeft(node.getLeft()));
            return rotateRight(node);
        }
       
        //AVL-Eigenschaft verletzt und es wurde im linken Teilbaum des linken Kindes eingefügt
        if(node.getBalance()>1 && node.getLeft()!=null && node.getLeft().getBalance()>0) {
            System.out.println("fall 4");
            return rotateRight(node);
        }
       
        System.out.println("return node: "+node.getElement());
        return node;

    }

    public void printPostorder() {
        printPostorder(root);

    }

    private void printPostorder(AVLTreeNode n) {
        if (n != null) {// tree not empty
            printPostorder(n.getLeft());
            printPostorder(n.getRight());
            println(n.getElement().toString());
        }
    }

   
    private AVLTreeNode rotateRight(AVLTreeNode node) {
        AVLTreeNode tmp = node.getLeft();
        node.setLeft(node.getLeft().getRight());
        tmp.setRight(node);
        return tmp;
    }

    private AVLTreeNode rotateLeft(AVLTreeNode node) {
        AVLTreeNode tmp = node.getRight();
        node.setRight(node.getRight().getLeft());
        tmp.setLeft(node);
        return tmp;
    }



}

public class AVLTreeNode {
       
        private Comparable elem;
        private AVLTreeNode left;
        private AVLTreeNode right;
        private int balance = 0;
        private int leftSubtreeHeight=0;
        private int rightSubtreeHeight=0;
       
        public AVLTreeNode(Comparable elem) {
            this.elem = elem;
            left = right = null;
       
        }

        public int getBalance() {
            calculateBalance();
            return balance;
        }
       
        private void calculateBalance() {
            if(this.getLeft()!=null && this.getRight()!=null) {
                if(this.getLeft().getLeft()!=null && this.getLeft().getRight()!=null){
                System.out.println("l höhe von: "+this.getLeft().getElement()+ ": "+this.getLeft().height());
                System.out.println("r höhe von: "+this.getRight().getElement()+": "+this.getRight().height());
                }
               
            balance=this.getLeft().height()-this.getRight().height();

            }
            if(this.getLeft()!=null && this.getRight()==null) {
                balance=this.getLeft().height();
            }
            if(this.getLeft()==null && this.getRight()!=null) {
                balance=-this.getRight().height();
            }
            if(this.getLeft()==null && this.getRight()==null) {
                balance=0;
            }
        }
       
        public int height() {
           
            if(this.getLeft()!=null) {
                leftSubtreeHeight=this.getLeft().height();
            }
            if(this.getRight()!=null) {
                rightSubtreeHeight=this.getRight().height();
            }
           
            //auf Maximum der Höhen für die Wurzel 1 addieren und Summe zurückgeben
            if(leftSubtreeHeight>rightSubtreeHeight || leftSubtreeHeight==rightSubtreeHeight) {
                return leftSubtreeHeight+1;
            }else {
                return rightSubtreeHeight+1;
            }
        }
       
        public AVLTreeNode getLeft() {
            return left;
        }

        public AVLTreeNode getRight() {
            return right;
        }

        public Comparable getElement() {
            return elem;
        }

        public void setLeft(AVLTreeNode n) {
            left = n;
        }

        public void setRight(AVLTreeNode n) {
            right = n;
        }
       
    }

Folgendes wird ausgegeben.



Vielen Dank im Voraus!

 

[mihe7]

Ein paar kleine Verbesserungen des Codes:

AVLTreeNode:

Der Gültigkeitsbereich von Variablen sollte immer so klein wie möglich sein: balance, leftSubtreeHeight und rigthSubtreeHeight kannst lokal halten. Instanzvariablen können zur Optimierung eingesetzt werden. Die kann man machen, wenn das Teil richtig funktioniert.

Insofern ergibt die Trennung von getHeight() und calculateBalance() hier auch (noch!) keinen Sinn, weil calculateBalance() nur und bei jedem Aufruf von getBalance() ausgeführt wird. Dabei unterscheidet sich getBalance() von calculateBalance() nur durch die Rückgabe der nicht benötigten Instanzvariablen.

In calculateBalance() selbst machst Du Dir das Leben unnötig schwer. Betrachte den Knoten mal als Balkenwaage. Der leere Knoten ist im Gleichgewicht und zeigt 0 an. Hängt man nun auf der linken Seite einen Teilbaum an den Knoten, erhöht sich das angezeigte Gewicht. Hängt man auf der rechten Seite einen Teilbaum an den Knoten, verringert sich das angezeigte Gewicht.

Macht:

        private int getBalance() {
            int balance = 0;
            if (this.getLeft() != null) {
                balance += getLeft().height();
            }
            if (this.getRigth() != null) {
                balance -= getRight().height();
            }
            return balance;
        }

Auch getHeight() lässt sich ein klein wenig vereinfachen, indem Du die die Bedingung anpasst. Hier kannst Du entweder gleich per >= vergleichen oder auf die Prüfung der Gleichheit ganz verzichten. Wenn leftSubtreeHeight == rightSubtreeHeight gilt, dann spielt es keine Rolle, welche Seite du verwendest.

            if(leftSubtreeHeight > rightSubtreeHeight) {

würde also reichen. Außerdem könnte man den ganzen if-Teil ersetzen:

            return (leftSubtreeHeight > rightSubtreeHeight ? leftSubtreeHeight : rightSubtreeHeight) + 1;
            // bzw.
            // return Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1;

AVLTree:

Von den Instanzvariablen ist keine unnötig, bei insert ist die Grundidee nicht schlecht, aber auf Methode komme ich gleich nochmal zurück...

Bei insertR fällt schon einmal die unschöne Bezeichnung auf. Da solltest Du was schöneres wählen. Wieder machst Du Dir dort das Leben unnötig schwer, durch die vielen Fallunterscheidungen. Davon kannst Du einige mit einer einfachen Überlegung erschlagen: was liefert ein Aufruf von insertR(null, elem)? Aktuell eine NullPointerException. Was könnte/sollte der Aufruf aber liefern? Warum nicht einfach einen neuen Knoten für das Element?

Hier einmal angedeutet:

    private AVLTreeNode insertR(AVLTreeNode node, Comparable elem) {
        if (node == null && elem != null) { 
            return new AVLTreeNode(elem);
        }

        int comparison = elem.compareTo(node.getElement());
        if (comparison < 0) {// left subtree
            node.setLeft(insertR(node.getLeft(), elem));
        } else if (comparison > 0) {
            node.setRight(insertR(node.getRight(), elem));
        }
// ...

Zurück zur insert-Methode; die ändert sich dadurch nämlich auch. Aus

    public void insert(Comparable elem) {
        if (root == null) {
            root = new AVLTreeNode(elem);
        } else {
            root = insertR(root, elem);
        }
        numberElements++;
    }

wird nun einfach

    public void insert(Comparable elem) {
        root = insertR(root, elem);
        numberElements++;
    }

Den funktionalen Teil habe ich mir nicht näher angesehen. Allerdings: die AVL-Eigenschaft wird nicht dadurch verletzt, dass die Balance < 1 ist. Da fehlt ein Minuszeichen.