Ankündigung

Einklappen
Keine Ankündigung bisher.

Avl

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Avl

    Ich habe ein Problem damit, ein Programm aus dem Buch "Algorithmen und Datenstrukturen" (5. überarbeitete Auflage) vom dpunkt.verlag zu verstehen.

    Es geht um das Einfügen eines Schlüssels in einen AVL-Baum.

    Hier der von Java nach PHP übersetzte Code:

    PHP-Code:
    <?php
       error_reporting
    (~0);
       
       class 
    Node
       
    {
          private 
    $key;
          public 
    $left// null|AVLNode null nur beim null-Knoten.
          
    public $right// null|AVLNode null nur beim null-Knoten.
          
          /**
           * @param null|int $key null nur beim head-Knoten.
           * @param null|AVLNode null nur beim null-Knoten.
           * @param null|AVLNode null nur beim null-Knoten.
           */
          
    function __construct($key$left null$right null)
          {
             
    $this->key $key;
             
    $this->left $left;
             
    $this->right $right;
          }
          
    /**
           * @return null|int
           */
          
    function getKey()
          {
             return 
    $this->key;
          }
       }
       
       class 
    AVLNode extends Node
       
    {  
          public 
    $balance 0// int {-1, 0, 1}
       
    }
       
       abstract class 
    ATree
       
    {  
          
    // head ist der oberste Knoten im Baum. Er gehört jedoch nicht zum Datenbestand, sondern
          // dient nur zum Einstieg in die Baumstruktur. Dieser Pseudo-Knoten verweist über das
          // rechte Kind zu den eigentlichen Daten.
          
    protected $headNode;
          
          
    // Hat ein Knoten keinen linken oder rechten Kind-Knoten, verweist auf einen null-Knoten.
          
    protected $nullNode;
          
          function 
    __construct()
          {
             
    // null-Knoten:
             
    $this->nullNode = new AVLNode(null);
             
             
    // Oberster Pseudo-Knoten der Datenstruktur:
             
    $this->headNode = new AVLNode(null$this->nullNode$this->nullNode);
          }
          
    /**
           * @param int $key Einzufügender Schlüssel.
           * @return bool Ob das Einfügen erfolgreich verlief.
           *    false, falls der neu einzufügende Schlüssel bereits im Baum existiert.
           */
          
    abstract function insert($key);
       }
       
       abstract class 
    ABinTree extends ATree
       
    {
          const 
    PREORDER 0;
          const 
    INORDER 1;
          const 
    POSTORDER 2;
          
          
    /**
           * Baum traversieren.
           * @param int $strategy PREORDER, INORDER oder POSTORDER
           * @return array Knoten-Sammlung
           */
          
    abstract function traverse($strategy self::INORDER);
       }
       
       class 
    AVLTree extends ABinTree
       
    {
          
    // rebalance zeigt an, ob die Balance-Werte aktualisiert und ein Unterbaum ev.
          // ausgeglichen werden muss. rebalance wird initialisiert, nachdem ein neuer
          // Schlüssel in den Baum eingefügt wurde bzw. der Schlüssel im Baum gefunden wurde.
          
    private $rebalance;
                
          
    // Ob das Einfügen erfolgreich verlief.
          
    private $success;
          
          
    /**
           * Einfache Rotation nach links. 3 Knoten müssen gedreht werden.
           * @param AVLNode $node Oberster der drei Knoten.
           * @return AVLNode Neuer oberster Knoten.
           */
          
    private static function rotateLeft(AVLNode $node)
          {
             
    $tmpNode $node->right;
             
    $node->right $node->right->left;
             
    $tmpNode->left $node;
             return 
    $tmpNode;
          }
          
    /**
           * Einfache Rotation nach rechts. 3 Knoten müssen gedreht werden.
           * @param AVLNode $node Oberster der drei Knoten.
           * @return AVLNode Neuer oberster Knoten.
           */
          
    private static function rotateRight(AVLNode $node)
          {
             
    $tmpNode $node->left;
             
    $node->left $node->left->right;
             
    $tmpNode->right $node;
             return 
    $tmpNode;
          }
          
    /**
           * Der neu einzufügende Schlüssel ist größer als der aktuelle Knoten.
           * Der Schlüssel muss im rechten Subbaum eingefügt werden.
           * @param AVLNode $node Ein rekursiv durchlaufener Knoten aus dem Baum.
           * @param int $key Einzufügender Schlüssel.
           * @return AVLNode
           */
          
    private function recInsertRight(AVLNode $node, &$key)
          {
             if(
    $node->right === $this->nullNode)
             {
                
    // Unten am Baum angelangt. Neuen Knoten definieren und im Baum anhängen.
                
    $node->right = new AVLNode($key$this->nullNode$this->nullNode);
                
    $this->success true;
                
                
    // Den balance-Wert von Knoten node aktualisieren.
                
    ++$node->balance;
                
    $this->rebalance $node->balance >= 1;
             }
             else
             {
                
    // Auf der rechten Seite ist ein Kind-Knoten vorhanden. Weiter runter im Baum.
                // Diese folgende Zuweisung wird benötigt, sobald ausgeglichen werden muss.
                // Fügt man nur einen neuen Knoten ein, ohne danach auszugleichen, ist diese
                // Zuweisung eigentlich unnötig.
                
    $node->right $this->recInsert($node->right$key);
                
                if
                (   
                   
    $node !== $this->headNode &&
                   
    $this->rebalance
                
    )
                {
                   switch(
    $node->balance)
                   {
                      case 
    1:
                         
    // Ausgleich erforderlich.
                         
    if($node->right->balance == 1)
                         {
                            
    // Einfache Links-Rotation.
                            
    $tmpNode self::rotateLeft($node);
                            
    $tmpNode->left->balance 0;
                         }
                         else
                         {
                            
    // Doppelte Links-Rotation (rechts/links-Rotation).
                            
    $balance $node->right->left->balance;
                            
                            
    $node->right self::rotateRight($node->right);
                            
    $tmpNode self::rotateLeft($node);
                            
    $tmpNode->right->balance $balance == -1
                               
    ?  1
                               
    :  0;
                            
    $tmpNode->left->balance $balance == 1
                               
    ?  -1
                               
    :  0;
                         }
                         return 
    $tmpNode;
                         
                      case -
    1:
                         
    // Sobald man im Baum eine balance -1 erreicht, sind alle
                         // balance-Werte im Baum auf den korrekten, aktuellen Stand.
                         
    $this->rebalance false;
                         
                      case 
    0:
                         
    // Bei 0 darf rebalance nicht false gesetzt werden.
                         // Das Ausgleichen muss im Baum nach oben hin propagiert werden.
                         
    ++$node->balance;
                   }
                }
                
    // Ansonst wird nur der Knote node zurückgegeben.
             
    }
             return 
    $node;
          }
          
    /**
           * Der neu einzufügende Schlüssel ist kleiner als der aktuelle Knoten.
           * Der Schlüssel muss im linken Subbaum eingefügt werden.
           * @param AVLNode $node Ein rekursiv durchlaufener Knoten aus dem Baum.
           * @param int $key Einzufügender Schlüssel.
           * @return AVLNode
           */
          
    private function recInsertLeft(AVLNode $node, &$key)
          {
             if(
    $node->left === $this->nullNode)
             {
                
    // Unten am Baum angelangt. Neuen Knoten definieren und im Baum anhängen.
                
    $node->left = new AVLNode($key$this->nullNode$this->nullNode);
                
    $this->success true;
                
                
    // Den balance-Wert von Knoten node aktualisieren.
                
    --$node->balance;
                
    $this->rebalance $node->balance <= -1;
             }
             else
             {
                
    // Auf der linken Seite ist ein Kind-Knoten vorhanden. Weiter runter im Baum.
                // Diese folgende Zuweisung wird benötigt, sobald ausgeglichen werden muss.
                // Fügt man nur einen neuen Knoten ein, ohne danach auszugleichen, ist diese
                // Zuweisung eigentlich unnötig.
                
    $node->left $this->recInsert($node->right$key);
                
                if
                (   
                   
    $node !== $this->headNode &&
                   
    $this->rebalance
                
    )
                {
                   switch(
    $node->balance)
                   {
                      case -
    1:
                         
    // Ausgleich erforderlich.
                         
    if($node->right->balance == -1)
                         {
                            
    // Einfache Rechts-Rotation.
                            
    $tmpNode self::rotateRight($node);
                            
    $tmpNode->right->balance 0;
                         }
                         else
                         {
                            
    // Doppelte Rechts-Rotation (links/rechts-Rotation).
                            
    $balance $node->left->right->balance;
                            
                            
    $node->left self::rotateLeft($node->left);
                            
    $tmpNode self::rotateRight($node);
                            
    // ??????? $tmpNode->right->balance = $balance == -1
                            //   ?  1
                            //   :  0;
                            // ??????$tmpNode->left->balance = $balance == 1
                            //   ?  -1
                            //   :  0;
                         
    }
                         return 
    $tmpNode;
                         
                      case 
    1:
                         
    // Sobald man im Baum eine balance 1 erreicht, sind alle
                         // balance-Werte im Baum auf den korrekten, aktuellen Stand.
                         
    $this->rebalance false;
                         
                      case 
    0:
                         
    // Bei 0 darf rebalance nicht false gesetzt werden.
                         // Das Ausgleichen muss im Baum nach oben hin propagiert werden.
                         
    --$node->balance;
                   }
                }
                
    // Ansonst wird nur der Knote node zurückgegeben.
             
    }
             return 
    $node;
          }
          
    /**
           * Beim Einfügen eines neuen Schlüssels wird der Baum rekursiv von oben nach unten
           * durchlaufen, bis jene Stelle gefunden wird, wo der neue Schlüssels
           * eingefügt werden kann.
           * @param AVLNode $node Ein rekursiv durchlaufener Knoten aus dem Baum.
           * @param int $key Einzufügender Schlüssel.
           * @return AVLNode
           */
          
    private function recInsert(AVLNode $node, &$key)
          {
             if(
    $key === $node->getKey())
             {
                
    // Der neu einzufügende Schlüssel existiert bereits im Baum.
                
    $this->rebalance $this->success false;
             }        
             elseif(
    $key $node->getKey())
             {
                
    // Weiter im rechten Subbaum.
                
    $node $this->recInsertRight($node$key);
             }
             else
             {
                
    // Weiter im linken Subbaum.
                
    $node $this->recInsertLeft($node$key);
             }
             return 
    $node;
          }
          
    /**
           * @param int $key Einzufügender Schlüssel.
           * @return bool Ob das Einfügen erfolgreich verlief.
           *    false, falls der neu einzufügende Schlüssel bereits im Baum existiert.
           */
          
    function insert($key)
          {
             
    $node $this->recInsert($this->headNode$key);
             return 
    $this->success;
          }
          
    /**
           * Knoten vor dem Traversieren der linken und rechten Unterbäume sammeln.
           * @param AVLNode $node
           * @param array $nodes Knoten-Sammlung
           */
          
    private function recTraversePreorder(AVLNode $node, array &$nodes)
          {
             if(
    $node !== $this->nullNode)
             {
                
    $nodes[] = $node;
                
    $this->recTraversePreorder($node->left$nodes);
                
    $this->recTraversePreorder($node->right$nodes);
             }
          }
          
    /**
           * Knoten zwischen dem Traversieren der linken und rechten Unterbäume sammeln.
           * @param AVLNode $node
           * @param array $nodes Knoten-Sammlung
           */
          
    private function recTraverseInorder(AVLNode $node, array &$nodes)
          {
             if(
    $node !== $this->nullNode)
             {
                
    $this->recTraverseInorder($node->left$nodes);
                
    $nodes[] = $node;
                
    $this->recTraverseInorder($node->right$nodes);
             }
          }
          
    /**
           * Knoten nach dem Traversieren der linken und rechten Unterbäume sammeln.
           * @param AVLNode $node
           * @param array $nodes Knoten-Sammlung
           */
          
    private function recTraversePostorder(AVLNode $node, array &$nodes)
          {
             if(
    $node !== $this->nullNode)
             {
                
    $this->recTraversePostorder($node->left$nodes);
                
    $this->recTraversePostorder($node->right$nodes);
                
    $nodes[] = $node;
             }
          }
          
    /**
           * Baum traversieren.
           * @param int $strategy PREORDER, INORDER oder POSTORDER
           * @return array Knoten-Sammlung
           */
          
    function traverse($strategy self::INORDER)
          {
             
    $nodes = [];
             switch(
    $strategy)
             {
                case 
    self::PREORDER:
                   
    $this->recTraversePreorder($this->headNode->right$nodes);
                   break;
                   
                case 
    self::INORDER:
                   
    $this->recTraverseInorder($this->headNode->right$nodes);
                   break;
                   
                case 
    self::POSTORDER:
                   
    $this->recTraversePostorder($this->headNode->right$nodes);
             }
             return 
    $nodes;
          }
       }
       
       
    $tree = new AVLTree();
       
    var_dump($tree->insert(1));
       
    var_dump($tree->insert(2));
       
    var_dump($tree->insert(3));
       
    $nodes $tree->traverse(AVLTree::PREORDER);
       foreach(
    $nodes as $node)
       {
          echo 
    $node->getKey(),", ",$node->balance,"<br />",PHP_EOL;
       }
    ?>
    Es geht mir mal um den ternären Operator in der Zeile 162. Ich verstehe die Wertzuweisungen nicht. Sind die ganz sicher richtig?


  • #2
    Was verstehst du daran nicht?
    Relax, you're doing fine.
    RTFM | php.de Wissenssammlung | Datenbankindizes | Dateien in der DB?

    Kommentar


    • #3
      Ich vermute es geht um den hier:

      PHP-Code:
      $tmpNode->right->balance $balance == -0
      Das ist übersetzt:

      PHP-Code:
      if ($balance == -1) {
          
      $tmpNode->right->balance 1;
      } else {
          
      $tmpNode->right->balance 0;

      Lerne Grundlagen | Schreibe gute Beispiele | PDO > mysqli > mysql | Versuch nicht, das Rad neu zu erfinden | Warum $foo[bar] böse ist | SQL Injections | Hashes sind keine Verschlüsselungen! | Dein E-Mail Regex ist falsch

      Kommentar


      • #4
        Was verstehst du daran nicht?
        Mir kommen die Werte seltsam vor, die zugewiesen werden. Ich würde da eigentlich andere Werte erwarten.
        Ich vermute es geht um den hier:
        Ja, um diese Anweisung geht es.

        Kommentar


        • #5
          Welche würdest du erwarten und warum?
          Wäre cool wenn man dir nicht alles aus der Nase ziehen muss.
          Relax, you're doing fine.
          RTFM | php.de Wissenssammlung | Datenbankindizes | Dateien in der DB?

          Kommentar


          • #6
            Nein, ich muss dir zustimmen, sieht nicht richtig aus. Wenn ich lokal in $balance den Wert "1" habe, macht es wenig Sinn im Objektattribut "balance" den Wert "-1" zu speichern. Aber lies doch mal im Buch nach bzw. probier es aus? Ich möchte jetzt nicht das komplette Script debuggen.

            Kommentar


            • #7
              Aber lies doch mal im Buch nach bzw. probier es aus?
              Ich kann es nicht ausprobieren, weil im Buch noch jener Teil fehlt, wo man im linken Subbaum einen Schlüssel einfügt. Ich habe schon angefangen, auch die dafür nötige Methode zu implementieren. Siehe Methode recInsertLeft. Aber dort bin ich mir auch nicht sicher, wie ich die balance-Werte aktualisieren muss.

              Kommentar


              • #8
                Hinweis:

                Der schließende Tag eines PHP-Blocks am Ende einer Datei ist optional. In einigen Fällen ist das Weglassen hilfreich:
                • Es können ungewollte Whitespaces am Ende einer Datei auftreten, durch die ein späteres setzen von headern be-/verhindert werden kann.
                • Außerdem verhindert dies, dass beim Output Buffering Whitespaces am Ende eines durch die eingebundenen Dateien erzeugten Parts.
                • Im PSR Standard (PSR-2) ist ?> sogar ausdrücklich verboten, wenn in einer Datei ausschliesslich PHP verwendet wird (2.2 Files).
                Standards - Best Practices - AwesomePHP - Guideline für WebApps

                Kommentar

                Lädt...
                X