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

[alhames]

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

@темы: PHP

Comments

[Itsygo]

а чего не автобаланс. бинарное?

[alhames]

Itsygo какое -какое? о_О

[La personne mystique]

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

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

[alhames]

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

[La personne mystique]

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

<?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);

?>

[La personne mystique]

<?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($binary, 60);
   bin_add($binary, 70);
   bin_add($binary, 10);
   
   var_dump ($binary);
   
?>

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

[Itsygo]

Itsygo какое -какое? о_О

ну, скажем AVL или Red-Black Binary tree. Короче сбалансированое дерево.

[Mclaud]

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

[La personne mystique]

Mclaud, конечно)

[alhames]

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

довольно длинный код...

<?php
class CVal {
    // инициализируем свойства, где $value - значение узла,
    // $left и $right - указатели на дочернии вершины
    var $value, $left, $right;

    // конструктор: создает новую вершину со значением $value
    function CVal($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }

    /************** методы класса: **************/
    // поиск $value
    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);
        }
    }
}
?>

[alhames]

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

[La personne mystique]

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

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

А как быть со скоростью?

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

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

пффф)

Вот, разобрал и прокомментировал приведенный тобой класс

ну, прокомментировать - прокомментировал, ты-то понял, почему так, а не иначе?))

[alhames]

La personne mystique

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

Неа, руки не дошли еще..

пффф)

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

ну, прокомментировать - прокомментировал, ты-то понял, почему так, а не иначе?))

Всмысле логику класса? Вообщем-то да =)

[Гость]

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

[Гость]

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