@ 2013-05-07T05:52:28Z <?php
$rb = new RBTree;
$inputs = array();
for ($i = 0; $i <= 100; ++$i) {
$key = mt_rand();
$value = mt_rand();
$rb->put($key, $value);
$inputs[] = $key;
}
for ($i = 0; $i <= 100; ++i) {
$key = mt_rand(0, 100);
var_dump($key, $rb->get($key));
echo "\n";
}
var_dump(101, $rb->get(101));
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.
Here you find the average performance (time & memory) of each version. A grayed out version indicates it didn't complete successfully (based on exit-code).
Version System time (s) User time (s) Memory (MiB) 5.4.14 0.011 0.042 12.06 5.4.13 0.009 0.041 12.04 5.4.12 0.009 0.038 12.00 5.4.11 0.009 0.039 12.00 5.4.10 0.010 0.038 12.00 5.4.9 0.013 0.047 12.00 5.4.8 0.008 0.046 12.00 5.4.7 0.011 0.036 11.99 5.4.6 0.012 0.037 12.00 5.4.5 0.009 0.039 11.99 5.4.4 0.012 0.034 11.98 5.4.3 0.008 0.040 11.98 5.4.2 0.015 0.043 11.98 5.4.1 0.014 0.052 11.98 5.4.0 0.010 0.039 11.47 5.3.24 0.011 0.048 12.72 5.3.23 0.014 0.044 12.71 5.3.22 0.011 0.048 12.68 5.3.21 0.013 0.039 12.68 5.3.20 0.011 0.041 12.68 5.3.19 0.010 0.049 12.68 5.3.18 0.014 0.050 12.67 5.3.17 0.012 0.039 12.67 5.3.16 0.014 0.042 12.67 5.3.15 0.011 0.044 12.67 5.3.14 0.010 0.044 12.66 5.3.13 0.013 0.044 12.66 5.3.12 0.013 0.062 12.66 5.3.11 0.010 0.039 12.66 5.3.10 0.009 0.045 12.12 5.3.9 0.011 0.041 12.09 5.3.8 0.011 0.041 12.08 5.3.7 0.010 0.043 12.07 5.3.6 0.009 0.046 12.07 5.3.5 0.011 0.040 12.00 5.3.4 0.010 0.046 12.00 5.3.3 0.011 0.044 11.95 5.3.2 0.010 0.041 11.72 5.3.1 0.017 0.052 11.68 5.3.0 0.009 0.042 11.67
preferences:dark mode live preview
141.76 ms | 1394 KiB | 7 Q