A persistent binary search tree in PHP

persistentTreePHP.php

<?php

abstract class Node{

	abstract public function __construct($left,$val,$right);
	abstract public function isEmpty();
	abstract public function insert($val);
	abstract public function member($val);

}

class EmptyNode extends Node{

	public function __construct($left = null,$val = null,$right = null){
		return;
	}

	public function isEmpty(){
		return true;
	}

	public function insert($val){
		return new Elem((new EmptyNode),$val,(new EmptyNode));
	}
	public function member($val){
		return false;
	}

}

class Elem extends Node{

	public $val;
	public $left;
	public $right;

	public function __construct($left,$val,$right){
		$this->val 		= $val;
		$this->left 	= $left;
		$this->right 	= $right;
	}

	public function isEmpty(){
		return false;
	}

	public function insert($val){
		if(is_object($val)){
			$val = clone $val;
		}

		if($this->val > $val){
			return new Elem($this->left->insert($val),$this->val,$this->right);
		}elseif ($this->val < $val) {
			return new Elem($this->left,$this->val,$this->right->insert($val));
		}else{
			return $this;
		}
	}
	public function member($val){
		if($this->val > $val){
			return $this->left->member($val);
		}elseif ($this->val < $val) {
			return $this->right->member($val);
		}else{
			return true;
		}
	}

}

function listTree(){
	$tree = new EmptyNode;
	foreach(range(1,10) as $i) {
		$tree = $tree->insert($i);
	}
	assert ($tree->val == 1);
	assert ($tree->right->val == 2);
	return $tree;
}
function test(){

	$tree = listTree();
	$newTree = $tree->insert(-1);
	assert ($newTree->left->val == -1);
	assert ($newTree->member(5));
	assert ($newTree->member(90) == false);
	assert ($tree->member(-1) == false and $newTree->member(-1));
}
test();

?>