Sign in to follow this  
Jouei

RB BST (red black binary search tree) (SOLVED)

Recommended Posts

Jouei    102
Hello there i have recently been developing a php based application and i find myself in need of a binary tree not such a hard thing to make but then i realized that all my results and ordered and that would make the tree incredibly unbalanced. So i set off to make an red and black tree since i heard this was a good option. Unforunitly for me some if not all of the refrences i found are ether A) not in php not such a bad thing but end up being poorly commented or not at all. or b) just a bit to confusing because of lack of information. i will post the code for my node structure and then i will continue on with what my problem is.

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;
}

}


So as you can see i managed to muddle out some of the much needed code eg: Rotation methods and a color check method. I can do do the color flips that are needed but what i am lost on is why and under what conditions does a rotation need to occur and what direction if one is needed. Also if there is anything i am missing i would very much well like to be informed as this has been one very large head ache for me given the lack of in coherent information. Regards Jouei. [Edited by - Jouei on April 30, 2010 11:21:53 PM]

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
not such a hard thing to make

Quote:
but then i realized that all my results and ordered and that would make the tree incredibly unbalanced. So i set off to make an red and black tree since i heard this was a good option.

Since it's might be a hard thing to make, why do you need a tree?

Quote:
not in php

PHP has associative arrays, which serve the role ordered trees serve in other languages.

Share this post


Link to post
Share on other sites
Jouei    102
Given that it holds data for different operations and page load time will be an issue a tree was decided to be used because of its fast search and return results.
the main reason for using a tree was because of speed. to keep load time low since it would be a global class and could hold the data we need for quick refrence as it may be used multiple times page load for refrences.

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Original post by Jouei
Given that it holds data for different operations and page load time will be an issue a tree was decided to be used because of its fast search and return results.
the main reason for using a tree was because of speed. to keep load time low since it would be a global class and could hold the data we need for quick refrence as it may be used multiple times page load for refrences.


Have you profiled how an array performs? It's implemented as a hash map, O(1) lookup, which is better than log(n) for trees.

For any bulk data, memcached is typically used.

Share this post


Link to post
Share on other sites
Jouei    102
Me and the other Programmer working on the project finally agreed as hash table would take up to much memory.

Given that every user logged in would have a copy of this data storage class this would up using memory as it is.

I did bring up a hash table but it was sead to end up using more memory then was necessarily needed.

That is why the RB BST was chosen.

[Edited by - Jouei on April 30, 2010 2:40:38 PM]

Share this post


Link to post
Share on other sites
stonemetal    288
Swing by wikipedia and check out AA trees. They are red black trees that have been simplified. The article does a pretty good job of explaining when to rotate etc.

Share this post


Link to post
Share on other sites
theOcelot    498
Quote:
Original post by Jouei...this has been one very large head ache for me given the lack of in coherent information.

But you're willing to continue slogging on for the sake of a hypothetical improvement in memory usage, which may or may not even matter? Why not just go with the hash map for now?

Share this post


Link to post
Share on other sites
Jouei    102
Thanks for the info on the AA Tree it was of great help i was able to implement one in a few hours -.^ a bit rusty with php classes apparently.

It is not a red black tree but from what i read performance is pritty close to the same.

Thanks a bunch and for all your help.

Regards Jouei.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this