   RB BST (red black binary search tree) (SOLVED)
  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 leafprotected $Key;//This nodes color Red if true, Black if falsepublic IsRed = false;//The left and right leafs below this onepublic  $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 blackif($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 upif($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 upif($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]
Quote:not such a hard thing to makeQuote: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.   ;  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.   ;Quote:Original post by JoueiGiven 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.   ;  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];  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.   ;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?   ;  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.   