Drzewa w PHP

Zaimplementowanie drzewiastej struktury z wykorzystaniem baz danych takich jak MySQL czy PostgreSQL nie jest trudnym zadaniem. Już po chwili zastanowienia przychodzi nam na myśl koncepcja, w której każdy element wskazuje na swojego rodzica. W implementacji tego drzewa potrzebujemy tylko dwa dodatkowe pola: id, parent_id. Przy wczytywaniu całości posługujemy się rekurencją. Skoro mamy tak przystępne rozwiązanie problemu czy warto poszukiwać czegoś innego? Jak najbardziej. O tym właśnie sobie pomówimy.

Można szybciej

Tradycyjne podejście ma jedną zasadniczą wadę. Zmusza nas abyśmy wykonali wiele zapytań do systemu bazodanowego. W prostych przypadkach jest to do zaakceptowania ale im większe mamy drzewo tym bardziej odczujemy skutki takiego wyboru. Z prostą reorganizacją zapisu drzewa możemy sytuację radykalnie poprawić.

Na rysunku zaprezentowałem drzewo z dodatkowymi parametrami left i right. Jeśli dany węzeł nie posiada potomka to jego wartość right jest większa od left o 1. Jeśli węzeł jest rodzicem jego parametr right musi być wystarczająco duży by pomieścić potomków. Dzięki takiej strukturze jesteśmy w stanie „poprosić” bazę danych o wszystkich potomków danej gałęzi za sprawą jednego zapytania.

SELECT * FROM `tree` WHERE `left` BETWEEN 1 AND 10 ORDER BY `left` ASC;

W wyniku zapytania otrzymujemy już posortowane dane. Możemy je wykorzystać w celu wyświetlenia drzewa. Poniżej prezentuję przykładowy kod PHP.

<?php

//$result - wynik zapytania
$right = array();//stos
foreach($result as $item)
{
    if(count($right) > 0)
        while($right[count($right)-1] < $item->right)
            array_pop($right);
    echo str_repeat('| ',count($right)).'';
    if(count($right) - 1 > 0)
    echo str_repeat('| ',count($right) - 1).'+- '.$item->name.'';
    else
        echo '+- '.$item->name.'';
    $right[] = $item->right;
}

Nie ma róży bez kolców. Nasze metoda jest bardzo szybka podczas czytania drzewa. Sama modyfikacja (przeniesienie/dodanie/usunięcie elementu) wymaga jednak sporego nakładu pracy. Każdemu z węzłów musimy zaktualizować parametry left i right. Ze swojego doświadczenia mogę zaproponować przechowywanie pomocniczego pola parent_id. Wtedy wszystkie czynności związane z przebudową są dużo prostsze w implementacji. Znając samą idee wierzę że jesteś w stanie napisać w tym celu odpowiednie funkcje samodzielnie.

Klasa Tree

Aby ułatwić sobie życie napisałem klasę upraszczającą korzystanie z drzewa. Zastosowałem w niej opisaną metodę. Zależało mi nie tylko na optymalizacji ale i elastyczności klasy. W wielu miejscach zrezygnowałem z przyśpieszenia kodu na rzecz wygody narzędzia. Klasa jest kompatybilna z Kohaną. Nie obsługuje jednak ORM. Jeśli zależy Ci na tej funkcjonalności polecam inne kompleksowe rozwiązanie.

Klasę dodajemy do naszego projektu wraz z przeniesieniem pliku Tree.php do katalogu/application/libraries/.

Publiczne metody:

• hasDescendants() – sprawdza czy węzeł posiada potomków.
• getChildren() – pobiera listę dzieci.
• getParent() – pobiera rodzica. Jeśli go nie ma zwraca false.
• getRoot() – pobiera korzeń.
• getDepth() – sprawdza jak głęboko znajduje się dany węzeł. Zwraca liczbę całkowitą.
• getPath($reverse=false) – pobiera tablicę elementów prowadzących do danego węzła. Kolejność może zostać odwrócona (domyślnie false).
• getNodeById($id) – odszukuje węzeł o podanym identyfikatorze. Przeszukiwana jest lista potomków danego węzła.
• move($item,$order=0,$parent=-1) – przenosi lub zmienia kolejność węzła. Metodę należy aktywować na korzeniu drzewa (id=parent_id). Argument $item oznacza przenoszoną gałąź. Jeśli parametr $item podamy jako liczbę uprzednio zostanie odszukany węzeł. Argument $order oznacza nową kolejność w danym rodzicu. Ostatni parametr umożliwia zmianę rodzica(domyślnie zasugerowany jest ten sam).
• insertItem($parent=-1) – dodajemy nowy węzeł. Domyślnie w korzeniu. Możemy manipulować miejscem pojawienia się dziecka za sprawą argumentu $parent.
• removeItem($item) – kolejna metoda obok move, insertItem, update, którą uruchamiamy dla korzenia. Parametr $item oznacza usuwany element.
• update($item) – zapisuje zmodyfikowane wartości podanego w argumencie węzła.

Klasa Tree posiada jeszcze jedną bardzo ważną właściwość: protected $table=””;. Jest to zmienna określająca tabelę, z której zostanie wczytane drzewo. Wraz z dziedziczeniem klasy nadpiszemy tą wartość. Wspomnijmy o samej tabeli. Narzuciłem konieczność istnienia pól: id, left, right, parent_id. Co jeśli chcesz mieć dodatkowe wartości? Żaden problem. Po prostu je dodaj klasa sama zadba o ich wczytywanie oraz zapisywanie. Przypominam że wszystkie zmiany na drzewie wykonujemy względem korzenia. Ten cechuje się id=parent_id.

Pora zająć się samym modelem dziedziczącym po naszej klasie Tree. Model Categories będzię czytał tabelę o tej samej nazwie. Ponadto rozszerzy funkcjonalność drzewa o dwie dodatkowe metody: prepareArray, prepareJson.

<?php

class Categories_Model extends Tree
{
    protected $table = 'categories';

    public function prepareJson()
    {
        return json_encode($this->prepareArray());
    }

    public function prepareArray($step=0,$temp=NULL,$childNodes=NULL,$child=NULL)
    {
        if ($step==0)
        {
            $child = $this;
            $temp = array();
            $temp['draggable'] = false;
        }

        $temp['id'] = $child->id;
        $temp['text'] = $child->text;
        $temp['left'] = $child->left;
        $temp['right'] = $child->right;
        $temp['leaf'] = !$child->hasDescendants();
        $temp['cls'] = $child->hasDescendants() ? 'folder':'file';
        if ($child->hasDescendants())
        {
            $temp['children'] = array();
            $children = $child->getChildren();
            foreach ($children as $child)
            {
                $step++;
                $this->prepareArray(&$step,&$temp['children'][],$children,$child);
                $step--;
            }
        }
        if ($step==0)
            return array($temp);
    }
}

Kontroler obsługujący nasz model.

<?php

class Welcome_Controller extends Controller
{
    private $categories;

    public function __construct()
    {
        parent::__construct();

        $this->template = new View('template');
        $this->template->body = new View('welcome');
        $this->categories=new Categories_Model();//domyślnie wczytujemy węzeł o id=1
    }

    public function index()
    {
        $this->template->body->tree = $this->categories->prepareArray();
        $this->template->render(TRUE);
    }

    public function add($id)
    {
        $item = $this->categories->insertItem($id);
        $item->text = "nowy".$item->id;
        $this->categories->update($item);
        url::redirect(url::base());
    }

    public function remove($id)
    {
        $this->categories->removeItem($id);
        url::redirect(url::base());
    }

    public function up($id)
    {
        $this->categories->move($id,0);
        url::redirect(url::base());
    }
}

Widok wyświetlający drzewo (welcome).

<?php

function htmlFromTree($tree,$step=0)
{
    if ($step==0)
    echo '';
 
    if ($tree['leaf']==0)
    {
        echo ''.$tree['text'].' ('.$tree['left'].','.$tree['right'].')';
        echo '';
        foreach ($tree['children'] as $item)
        {
            $step++;
            htmlFromTree($item,$step);
            $step--;
        }
        echo '';
    }
    else
        echo ''.$tree['text'].' ('.$tree['left'].','.$tree['right'].')';
 
    if ($step==0)
        echo '';
}

if (isset($tree))
    htmlFromTree($tree[0]);

Załączniki

• Tree.php
• Drzewo – Kohana

Do następnego razu.