class bst_leaf
{
//The key value of this leaf
protected $Key;

//This nodes color Red if true, Black if false
public IsRed = false;
//The left and right leafs below this one
public  $Left = null;
public  $Right = null;

protected $Data = null;

function __construct($Key, $Data)
{
$this->Key - Key;
$this->Data = $Data;
}

public function GetKey()
{
return $this->Key;
}

public function getData()
{
return $this->Player_Data;
}

public function Search($Key)
{
	if($Key == $this->Key)
	{
		return $this->Data;
	}
	if($Key < $this->Key)
	{
		return $this->Left->Search($Key);
	}
	else
	{
		return $this->Right->Search($Key);
	}
	return null;
}

public function Update($Key, $Data)
{
	if($Key == $this->Key)
	{
		$this->Data = $Data;
		return true;
	}
	if($Key < $this->Key)
	{
		return $this->Left->Update($Key, $Data);
	}
	else
	{
		return $this->Right->Update($Key, $Data);
	}
	
	return false;
}

public function Insert($Key,$Data)
{
	//Check the color rule if the it fails change children to black
	if($this->ColorCheck())
	{
		$this->Left->IsRed = false;
		$this->Right->IsRed = false;
		$this->IsRead = true;
	}
	
	if($Key < $this->Key)
	{
		if($this->Left != null)
		{
			$this->Insert($Key,$Data);
		}
		else
		{
			$this->Left = new bst_leaf($Key,$Data);
		}
		
	}
	else
	{
		if($this->Right != null)
		{
			$this->Insert($Key,$Data);
		}
		else
		{
			$this->Right = new bst_leaf($Key,$Data);
		}
	}
}

public function ColorCheck()
{
	if($this->IsRed == false)
	{
		return false;
	}
	
	if($this->IsRed == true && $this->Left == null && $this->Right == null)
	{
	
	}

	if($this->IsRed == true && $this->Left->IsRed == false && $this->Right->IsRed == false)
	{
		return false;
	}
	
	return true;
}

public function RotateLeft()
{
//top one needs to go down to the Left and the Right needs to come up
if($this->Left == null)
return;

$TempLeft = $this->Left;
$this->Left = $this;
$this->Left->Left = $TempLeft;
$this = $this->Right;
}

public function RotateRight()
{
//top one needs to go down to the Right and the Left needs to come up
if($this->Right == null)
return;

$TempRight = $this->Right;
$this->Right = $this;
$this->Right->Right = $TempRight;
$this = $this->Left;
}

}