@ 2013-05-07T05:46:26Z <?php
class Node
{
public $color;
public $key;
public $value;
public $left;
public $right;
public function __construct($key, $value, $color)
{
$this->key = $key;
$this->value = $value;
$this->color = $color;
}
public function compare($key)
{
if ($this->key < $key) return -1;
elseif ($this->key > $key) return 1;
else return 0;
}
}
class RBTree
{
const RED = true;
const BLACK = false;
private $root;
public function isEmpty()
{
return $this->root == null;
}
public function put($key, $value)
{
$this->root = $this->insert($this->root, (int)$key, $value);
$this->root->color = self::BLACK;
}
public function get($key)
{
$x = $this->search($this->root, (int)$key);
return $x ? $x->value : null;
}
private function isRed($h)
{
return $h ? $h->color : false;
}
private function insert($x, $key, $value)
{
if (!$x) return new Node($key, $value, self::RED);
$cmp = $x->compare($key);
if ($cmp > 0) $x->right = insert($x->right, $key, $value);
elseif ($cmp < 0) $x->left = insert($x->left, $key, $value);
else $x->value = $value;
if ($this->isRed($x->right) && !$this->isRed($x->left)) $x = $this->rotateLeft($x);
if ($this->isRed($x->left) && $this->isRed($x->left->left)) $x = $this->rotateRight($x);
if ($this->isRed($x->left) && $this->isRed($x->right)) $this->flipColors($x);
return $x;
}
private function search($x, $key)
{
while ($x) {
$cmp = $x->compare($key);
if ($cmp > 0) $x = $x->right;
elseif ($cmp < 0) $x = $x->left;
else return $x;
}
return null;
}
private function flipColors($h)
{
$h->color = !$h.color;
$h->left->color = !$h->left->color;
$h->right->color = $h->right->color;
}
private function rotateLeft($h)
{
$x = $h->right;
$h->right = $x->left;
$x->left = $h;
$x->color = $x->left->color;
$x->left->color = self::RED;
return $x;
}
private function rotateRight($h)
{
$x = $h->left;
$h->left = $x->right;
$x->right = $h;
$x->color = $x->right->color;
$x->right->color = self::RED;
return $x;
}
}
Enable javascript to submit You have javascript disabled. You will not be able to edit any code.
Output for 5.0.0 - 5.0.5 , 5.1.0 - 5.1.6 , 5.2.0 - 5.2.17 , 5.3.0 - 5.3.29 , 5.4.0 - 5.4.45 , 5.5.24 - 5.5.35 , 5.6.8 - 5.6.28 , 7.0.0 - 7.0.20 , 7.1.0 - 7.1.10 , 7.2.0 - 7.2.33 , 7.3.12 - 7.3.33 , 7.4.0 - 7.4.33 , 8.0.0 - 8.0.30 , 8.1.0 - 8.1.27 , 8.2.0 - 8.2.17 , 8.3.0 - 8.3.4 Output for 4.4.2 - 4.4.9 Parse error: syntax error, unexpected T_STRING, expecting T_OLD_FUNCTION or T_FUNCTION or T_VAR or '}' in /in/pmKqN on line 4
Process exited with code 255 . Output for 4.3.0 - 4.3.1 , 4.3.5 - 4.3.11 , 4.4.0 - 4.4.1 Parse error: parse error, unexpected T_STRING, expecting T_OLD_FUNCTION or T_FUNCTION or T_VAR or '}' in /in/pmKqN on line 4
Process exited with code 255 . Output for 4.3.2 - 4.3.4 Parse error: parse error, expecting `T_OLD_FUNCTION' or `T_FUNCTION' or `T_VAR' or `'}'' in /in/pmKqN on line 4
Process exited with code 255 . preferences:dark mode live preview
194.06 ms | 401 KiB | 309 Q