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:
Es geht mir mal um den ternären Operator in der Zeile 162. Ich verstehe die Wertzuweisungen nicht. Sind die ganz sicher richtig?
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;
}
?>
Kommentar