<?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 = $this->insert($x->right, $key, $value);
elseif ($cmp < 0) $x->left = $this->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;
}
}
preferences:
29.08 ms | 402 KiB | 5 Q