20:14 

Бинарные деревья на PHP

alhames
alhames.ru
Чет тихо.. Вот, чтоли, для разнообразия:
Итак, задача такая - реализовать на PHP бинарное дерево.
Как я понимаю, самый удачный способ - использовать ООП.
Так как в ООП я чайник, так что сейчас буду разбираться.
Хотелось бы увидеть ваши варианты реализации :)

@темы: PHP

Комментарии
2008-04-17 в 20:22 

Itsygo
Geza Anda pl Mozart-PC 21 in CM K467-I Allegro Maestoso[13:54].flac
а чего не автобаланс. бинарное?

2008-04-17 в 20:52 

alhames
alhames.ru
Itsygo какое -какое? о_О

2008-04-17 в 20:55 

 
а почему ООП и чем тебе не угодили хэши (a.k.a. массивы)? )

P.S. я без претензий, я просто не люблю ООП =)

2008-04-17 в 21:08 

alhames
alhames.ru
La personne mystique ну, есть две причины: в ООП реализовать все проще и более нагляднее - это первое. А второе - мой препод ООП "любит" (так как сам в нём с трудом шарит) =)

2008-04-17 в 21:32 

 
ну, все равно функции-то будут как близнецы.) разница в форме. мне постоянно кажется, что, используя классы для таких мелочей, я теряю кучу ресурсов (хотя я не уверен, всегда ли это действительно так). да и в структуре классов часто путаюсь.

<?php

   
class CVal
   
{
      var 
$value$left$right;
     
      function 
CVal($value)
      {
         
$this->value $value;
         
$this->left null;
         
$this->right null;
      }
     
     
// worker funcs
     
function find($value)
      {
         if (
$this->value == $value)
            return 
TRUE;
         elseif (
$value $this->value)
            return 
$this->left $this->left->find($value) : FALSE;
         else
            return 
$this->right $this->right->find($value) : FALSE;
      }
     
      function 
add($value)
      {
         if (
$value $this->value)
         {
            if (
$this->left)
               
$this->left->add($value);
            else
               
$this->left = new CVal($value);
         }
         else
         {
            if (
$this->right)
               
$this->right->add($value);
            else
               
$this->right = new CVal($value);
         }
      }
   }

   
$binary = new CVal(50);
   
$binary->add(60);
   
$binary->add(70);
   
$binary->add(10);
   
   
var_dump ($binary);

?>

2008-04-17 в 21:33 

 
<?php

   
function bin_create($value)
   {
      return array(
'value' => $value);
   }
   
   function 
bin_add(&$binary$value)
   {
      if (
$value $binary['value'])
         
$frame 'left';
      else
         
$frame 'right';
      if (isset(
$binary[$frame]))
         
bin_add($binary[$frame], $value);
      else
         
$binary[$frame] = bin_create($value);
   }
   
   function 
bin_find(&$binary$value)
   {
      if (
$binary['value'] == $value)
         return 
TRUE;
      elseif (
$value $binary['value'])
         return 
bin_find($binary['left'], $value);
      else
         return 
bin_find($binary['right'], $value);
   }
   
// etc
   
   
$binary bin_create(50);
   
bin_add($binary60);
   
bin_add($binary70);
   
bin_add($binary10);
   
   
var_dump ($binary);
   
?>


это, ест-но, не полная реализация, просто для примера. )

2008-04-18 в 04:11 

Itsygo
Geza Anda pl Mozart-PC 21 in CM K467-I Allegro Maestoso[13:54].flac
Itsygo какое -какое? о_О
ну, скажем AVL или Red-Black Binary tree. Короче сбалансированое дерево.

2008-04-23 в 07:58 

Mclaud
La personne mystique, офигеть, и ты это ООП называешь?

2008-04-23 в 12:20 

 
Mclaud, конечно)

2008-05-14 в 19:10 

alhames
alhames.ru
La personne mystique такс.. Наконец у меня руки до ООП дошли..
Вот, разобрал и прокомментировал приведенный тобой класс.
довольно длинный код...

2008-05-14 в 19:54 

alhames
alhames.ru
La personne mystique собственно, у структурного программирования логика таже, но помоему устройство сложнее.. А как быть со скоростью?
Впрочем, она мне не столь важна.. Теперь буду делать это:
"Вершины дерева вещественные числа. Описать функцию, которая:
a) вычисляет среднее арифметическое всех вершин дерева;
b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции)."

2008-05-18 в 23:12 

 
собственно, у структурного программирования логика таже, но помоему устройство сложнее..
по сути мой второй пример тоже являет собой ООП, только на более низком уровне)

А как быть со скоростью?
а ты замерял, что быстрее работает и насколько?

Теперь буду делать это:
пффф)


Вот, разобрал и прокомментировал приведенный тобой класс
ну, прокомментировать - прокомментировал, ты-то понял, почему так, а не иначе?))

2008-05-18 в 23:33 

alhames
alhames.ru
La personne mystique
а ты замерял, что быстрее работает и насколько?
Неа, руки не дошли еще..

пффф)
Вот-вот.. У мну творческий кризис из-за болезни =(

ну, прокомментировать - прокомментировал, ты-то понял, почему так, а не иначе?))
Всмысле логику класса? Вообщем-то да =)

2011-12-19 в 19:00 

Мало чувств.. но красиво…

URL
2013-11-25 в 11:42 

какое же здесь ООП, если не указано можно сказать главное, один из основополагающих принципов ООП?
Слышали об инкапсуляции? неплохо было бы прописать для всех переменных и функций в классе степень защищенности от несанкционированного доступа...

URL
     

@web-программирование

главная