tree

  1 二叉查找树
  2 <?php
  3 
  4     /**
  5      * 节点类
  6      */
  7     class Node
  8     {
  9         public $val;
 10         public $left;
 11         public $right;
 12 
 13         public function __construct( $val )
 14         {
 15             $this->val  = $val;            
 16         }
 17     }
 18 
 19     /**
 20      * 二叉搜索树；
 21      */
 22     class SearchTree
 23     {
 24         private $_root; //根节点
 25 
 26         public function __construct()
 27         {
 28             $this->_root    = null;
 29         }
 30 
 31         public function insert( $val )
 32         {
 33             $this->_root = $this->_insert( $val, $this->_root );
 34             return $this->_root;
 35         }
 36 
 37         private function _insert( $val, $tree )
 38         {
 39             if( $tree == null ) {
 40                 $node   = new Node( $val );
 41                 return $node;
 42             }
 43 
 44             if( $val > $tree->val ) {
 45                 $tree->right    = $this->_insert( $val, $tree->right );
 46             }else if( $val < $tree->val ) {
 47                 $tree->left     = $this->_insert( $val, $tree->left );
 48             }else {
 49                 // do nothing.
 50             }
 51             return $tree;
 52         }
 53 
 54         public function find( $x )
 55         {
 56             return $this->_find( $x, $this->_root );
 57         }
 58 
 59         private function _find( $x, $tree )
 60         {
 61             if( $tree == null )
 62                 return null;
 63             
 64             if( $tree->val == $x ) 
 65                 return $tree;
 66             else if( $tree->val > $x ) {
 67                 return $this->_find( $x, $tree->left );
 68             }else {
 69                 return $this->_find( $x, $tree->right );
 70             }
 71         }
 72 
 73         public function findMax()
 74         {
 75             $tmp    = $this->_root;
 76             while( $tmp && $tmp->right ) {
 77                 $tmp    = $tmp->right;
 78             }
 79 
 80             return $tmp;
 81         }
 82 
 83         public function findMin( $tree = null )
 84         {
 85             $tmp    = $tree ? $tree : $this->_root;
 86             while( $tmp && $tmp->left ) {
 87                 $tmp    = $tmp->left;
 88             }
 89 
 90             return $tmp;
 91         }
 92 
 93         public function delete( $x )
 94         {
 95             $this->_root    = $this->_delete( $x, $this->_root );
 96             return $this->_root;
 97         }
 98 
 99         public function _delete( $x, $tree )
100         {
101             if( $tree == null )
102                 return $tree;
103             
104             if( $x > $tree->val ) {
105                 $tree->right    =  $this->_delete( $x, $tree->right );
106             }else if( $x < $tree->val ) {
107                 $tree->left     =  $this->_delete( $x, $tree->left );
108             }else {
109                 //删除节点。
110                 if( $tree->left == null && $tree->right == null ) {
111                     //叶子节点，直接删除
112                     $tree   = null;
113                     return $tree;
114                 }
115 
116                 if( $tree->left == null ) {
117                     $tree   = $tree->right;
118                 }else if( $tree->right == null ) {
119                     $tree   = $tree->left;
120                 }else {
121                     //左右都有子节点。右边找最小子节点 代替当前节点
122                     $rightMin   = $this->findMin( $tree->right );
123                     $tree->right        = $this->_delete( $rightMin->val, $tree->right );
124                     $rightMin->left     = $tree->left;
125                     $rightMin->right    = $tree->right;
126                     $tree       = $rightMin;
127                     unset( $rightMin ); 
128                 }
129             }
130             return $tree;
131         }
132 
133         /**
134          * 中序输出
135          */
136         public function inEcho()
137         {
138             $this->_inEcho( $this->_root );
139             echo ‘~~~~~~~~~~ ‘ . PHP_EOL;
140         }
141 
142         private function _inEcho( $tree )
143         {
144             if( $tree == null ) {
145                 return;
146             }
147 
148             $this->_inEcho( $tree->left );
149             echo $tree->val . PHP_EOL;
150             $this->_inEcho( $tree->right );
151         }
152 
153         public function dump()
154         {
155             $ret    = [];
156             if( $this->_root == null )
157                 return $ret;
158 
159             $stack  = new SplStack();
160             $stack->push( [$this->_root] );
161             while( !$stack->isEmpty() ) {
162                 $node   = $stack->pop();
163 
164                 $temp   = $stackVal = [];
165                 $isAllNull  = true;
166                 foreach( $node as $_node ) {
167                     if( $_node == null )
168                         $temp[]     = ‘‘;
169                     else {
170                         $temp[]     = $_node->val;
171                         $isAllNull  = false;
172                     }
173 
174                     if( $_node && $_node->left ) {
175                         $stackVal[]     = $_node->left;
176                     }else {
177                         $stackVal[]     = null;
178                     }
179                     if( $_node && $_node->right ) {
180                         $stackVal[]     = $_node->right;
181                     }else {
182                         $stackVal[]     = null;
183                     }
184                 }
185                 if( !$isAllNull ) {
186                     if( $stackVal ) $stack->push( $stackVal );
187                     if( $temp ) $ret[]  = $temp;
188                 }
189             }
190 
191             $retCount   = count( $ret ) - 1;
192             foreach( $ret as $_retVal ) {
193                 echo str_repeat( ‘  ‘, $retCount );
194                 $_retValCount   = count( $_retVal );
195                 $_tempEcho = ‘‘;
196                 for( $i = 0; $i < $_retValCount; $i+= 2 ) {
197                     $_tempEcho .= ‘|‘;
198                     if( isset( $_retVal[$i+1] ) ){
199                         $_tempEcho .=  $_retVal[$i] . ‘-‘ . $_retVal[$i+1];
200                     }else 
201                         $_tempEcho .=  $_retVal[$i];
202                     $_tempEcho .=  ‘|‘;
203                 }
204                 echo str_replace( ‘||‘, ‘|‘, $_tempEcho );
205                 $retCount--;
206                 echo PHP_EOL;
207             }
208         }
209 
210     }
211 
212 
213     $tree   = new SearchTree();
214     $tree->insert( 100 );
215     $tree->insert( 20 );
216     $tree->insert( 30 );
217     $tree->insert( 15 );
218     $tree->insert( 5 );
219     $tree->insert( 90 );
220     $tree->insert( 17 );
221     $tree->insert( 18 );
222     $tree->insert( 188 );
223     $tree->dump();
224     // $tree->delete( 100 );
225     // $tree->dump();
226     // var_dump( $tree->find( 150 ) );
227     var_dump( $tree->findMax() );

  1 avl树
  2 <?php
  3     class Node
  4     {
  5         public $val;
  6         public $left;
  7         public $right;
  8         public $height;
  9 
 10         public function __construct( $val )
 11         {
 12             $this->val  = $val;
 13             $this->height   = 0;
 14         }
 15     }
 16 
 17 
 18     class AvlTree
 19     {
 20         private $_root;
 21 
 22         public function __construct()
 23         {
 24             $this->_root    = null;
 25         }
 26 
 27         public function find( $x )
 28         {
 29             return $this->_find( $x, $this->_root );
 30         }
 31 
 32         private function _find( $x, $tree )
 33         {
 34             if( $tree == null )
 35                 return null;
 36             
 37             if( $tree->val == $x ) 
 38                 return $tree;
 39             else if( $tree->val > $x ) {
 40                 return $this->_find( $x, $tree->left );
 41             }else {
 42                 return $this->_find( $x, $tree->right );
 43             }
 44         }
 45 
 46         public function findMax()
 47         {
 48             $tmp    = $this->_root;
 49             while( $tmp && $tmp->right ) {
 50                 $tmp    = $tmp->right;
 51             }
 52 
 53             return $tmp;
 54         }
 55 
 56         public function findMin( $tree = null )
 57         {
 58             $tmp    = $tree ? $tree : $this->_root;
 59             while( $tmp && $tmp->left ) {
 60                 $tmp    = $tmp->left;
 61             }
 62 
 63             return $tmp;
 64         }
 65 
 66         public function getHeight( $tree ) {
 67             if( $tree == null )
 68                 return -1;
 69             else 
 70                 return $tree->height;
 71         }
 72 
 73         public function insert( $x )
 74         {
 75             $this->_root = $this->_insert( $x, $this->_root );
 76             return $this->_root;
 77         }
 78 
 79         private function _insert( $val, $tree )
 80         {
 81             if( $tree == null ) {
 82                 $node   = new Node( $val );
 83                 return $node;
 84             }
 85 
 86             if( $val > $tree->val ) {
 87                 $tree->right    = $this->_insert( $val, $tree->right );
 88                 if( $this->getHeight( $tree->right ) - $this->getHeight( $tree->left ) == 2 ) {
 89                     if( $val > $tree->right->val ) {
 90                         // var_dump( "val = {$val} ;; rotate = singleRotateWithRight ");
 91                         $tree = $this->singleRotateWithRight( $tree ); 
 92                     }else {
 93                         // var_dump( "val = {$val} ;; rotate = doubleRotateWithRight ");
 94                         $tree = $this->doubleRotateWithRight( $tree ); 
 95                     }
 96                 }
 97             }else if( $val < $tree->val ) {
 98                 $tree->left     = $this->_insert( $val, $tree->left );
 99                 if( $this->getHeight( $tree->left ) - $this->getHeight( $tree->right ) == 2  ) {
100                     if( $val < $tree->left->val ) {
101                         // var_dump( "val = {$val} ;; rotate = singleRotateWithLeft ");
102 
103                         $tree = $this->singleRotateWithLeft( $tree ); 
104                     }else {
105                         // var_dump( "val = {$val} ;; rotate = doubleRotateWithLeft ");
106 
107                         $tree = $this->doubleRotateWithLeft( $tree ); 
108                     }
109                 }
110             }else {
111                 // do nothing.
112             }
113             
114             $tree->height    = max( $this->getHeight( $tree->left ), $this->getHeight( $tree->right ) ) + 1;
115 
116             return $tree;
117         }
118 
119         private function singleRotateWithRight( $tree )
120         {
121             $newRoot        = $tree->right;
122             $tree->right    = $newRoot->left;
123             $newRoot->left  = $tree;
124 
125             $newRoot->height    = max( $this->getHeight( $newRoot->left ), $this->getHeight( $newRoot->right ) ) + 1;
126             $tree->height    = max( $this->getHeight( $tree->left ), $this->getHeight( $tree->right ) ) + 1;
127 
128             return $newRoot;
129         }
130 
131         private function singleRotateWithLeft( $tree )
132         {
133             $newRoot        = $tree->left;
134             $tree->left     = $newRoot->right;
135             $newRoot->right = $tree;
136 
137             $newRoot->height    = max( $this->getHeight( $newRoot->left ), $this->getHeight( $newRoot->right ) ) + 1;
138             $tree->height    = max( $this->getHeight( $tree->left ), $this->getHeight( $tree->right ) ) + 1;
139 
140             return $newRoot;
141         }
142 
143         private function doubleRotateWithRight( $tree )
144         {
145             $tree->right    = $this->singleRotateWithLeft( $tree->right );
146             return $this->singleRotateWithRight( $tree );
147         }
148 
149         private function doubleRotateWithLeft( $tree )
150         {
151             $tree->left     = $this->singleRotateWithRight( $tree->left );
152             return $this->singleRotateWithLeft( $tree );
153         }
154 
155         public function dump()
156         {
157             $ret    = [];
158             if( $this->_root == null )
159                 return $ret;
160 
161             $stack  = new SplStack();
162             $stack->push( [$this->_root] );
163             while( !$stack->isEmpty() ) {
164                 $node   = $stack->pop();
165 
166                 $temp   = $stackVal = [];
167                 $isAllNull  = true;
168                 foreach( $node as $_node ) {
169                     if( $_node == null )
170                         $temp[]     = ‘‘;
171                     else {
172                         $temp[]     = $_node->val;
173                         $isAllNull  = false;
174                     }
175 
176                     if( $_node && $_node->left ) {
177                         $stackVal[]     = $_node->left;
178                     }else {
179                         $stackVal[]     = null;
180                     }
181                     if( $_node && $_node->right ) {
182                         $stackVal[]     = $_node->right;
183                     }else {
184                         $stackVal[]     = null;
185                     }
186                 }
187                 if( !$isAllNull ) {
188                     if( $stackVal ) $stack->push( $stackVal );
189                     if( $temp ) $ret[]  = $temp;
190                 }
191             }
192 
193             $retCount   = count( $ret ) - 1;
194             foreach( $ret as $_retVal ) {
195                 echo str_repeat( ‘  ‘, $retCount );
196                 $_retValCount   = count( $_retVal );
197                 $_tempEcho = ‘‘;
198                 for( $i = 0; $i < $_retValCount; $i+= 2 ) {
199                     $_tempEcho .= ‘|‘;
200                     if( isset( $_retVal[$i+1] ) ){
201                         $_tempEcho .=  $_retVal[$i] . ‘-‘ . $_retVal[$i+1];
202                     }else 
203                         $_tempEcho .=  $_retVal[$i];
204                     $_tempEcho .=  ‘|‘;
205                 }
206                 echo str_replace( ‘||‘, ‘|‘, $_tempEcho );
207                 $retCount--;
208                 echo PHP_EOL;
209             }
210         }
211 
212         public function delete( $x )
213         {
214             $this->_root    = $this->_delete( $x, $this->_root );
215             return $this->_root;
216         }
217 
218         private function _delete( $val, $tree )
219         {
220             if( $tree == null )
221                 return $tree;
222             
223             if( $val > $tree->val ) {
224                 $tree->right    = $this->_delete( $val, $tree->right );
225                 if( $this->getHeight( $tree->right ) - $this->getHeight( $tree->left ) == 2 ) {
226                     if( $val > $tree->right->val ) {
227                         $tree = $this->singleRotateWithRight( $tree ); 
228                     }else {
229                         $tree = $this->doubleRotateWithRight( $tree ); 
230                     }
231                 }
232             }else if( $val < $tree->val ) {
233                 $tree->left     = $this->_delete( $val, $tree->left );
234                 if( $this->getHeight( $tree->left ) - $this->getHeight( $tree->right ) == 2 ) {
235                     if( $val < $tree->left->val ) {
236                         $tree = $this->singleRotateWithLeft( $tree ); 
237                     }else {
238                         $tree = $this->doubleRotateWithLeft( $tree ); 
239                     }
240                 }
241                 
242             }else {
243                 if( $tree->left == null && $tree->right == null ) {
244                     $tree = null;
245                     return $tree;
246                 }
247                 if( $tree->left == null ) {
248                     $tree   = $tree->right;
249                 }else if( $tree->right == null ) {
250                     $tree   = $tree->left;
251                 }else {
252                     $rightMin   = $this->findMin( $tree->right );
253                     $tree->right    = $this->_delete( $rightMin->val, $tree->right );
254                     $rightMin->left     = $tree->left;
255                     $rightMin->right    = $tree->right;
256 
257                     $tree   = $rightMin;
258                 }
259             }
260 
261             $tree->height    = max( $this->getHeight( $tree->left ), $this->getHeight( $tree->right ) ) + 1;
262             return $tree;
263         }
264     }
265 
266 
267     $tree = new AvlTree();
268     $tree->insert(3);
269     $tree->insert(2);
270     $tree->insert(1);
271     $tree->insert(4);
272     $tree->insert(5);
273     $tree->insert(6);
274     $tree->insert(7);
275     $tree->insert(16);
276     $tree->insert(15);
277     $tree->insert(14);
278     $tree->insert(13);
279     $tree->insert(12);
280     $tree->insert(11);
281     $tree->insert(10);
282     $tree->insert(8);
283     $tree->insert(9);
284 
285     $tree->delete(7);
286     $tree->delete(8);
287 
288     $tree->dump();
289     // var_dump( $tree );