Como usar árvores em PHP

Árvores são estruturas de dados não lineares que organizam os dados de forma hierárquica. Elas são muito úteis para resolver diversos problemas, como busca, ordenação, armazenamento e processamento de dados. Neste post, vamos aprender como implementar alguns tipos de árvores em PHP e ver alguns exemplos de uso.

Árvore binária

Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos. Ela é usada para implementar operações de busca, inserção e remoção eficientes. Para representar uma árvore binária em PHP, podemos usar uma classe que tenha um valor e dois atributos para os filhos esquerdo e direito. Por exemplo:

class No {
  public $valor;
  public $esquerdo;
  public $direito;

  public function __construct($valor) {
    $this->valor = $valor;
    $this->esquerdo = null;
    $this->direito = null;
  }
}

Para criar uma árvore binária, podemos instanciar objetos da classe No e atribuir os filhos esquerdo e direito conforme a regra da árvore. Por exemplo, para criar a seguinte árvore binária:

    10
   /  \
  5    15
 / \     \
3   7     20

Podemos fazer:

$raiz = new No(10);
$raiz->esquerdo = new No(5);
$raiz->direito = new No(15);
$raiz->esquerdo->esquerdo = new No(3);
$raiz->esquerdo->direito = new No(7);
$raiz->direito->direito = new No(20);

Para percorrer uma árvore binária, podemos usar diferentes métodos, dependendo da ordem que queremos visitar os nós. Os mais comuns são:

• Travessia em ordem: visita o filho esquerdo, o nó atual e o filho direito. É usada para obter os valores da árvore em ordem crescente.
• Travessia pré-ordem: visita o nó atual, o filho esquerdo e o filho direito. É usada para copiar ou clonar a árvore.
• Travessia pós-ordem: visita o filho esquerdo, o filho direito e o nó atual. É usada para liberar a memória da árvore.

Para implementar esses métodos em PHP, podemos usar funções recursivas que recebem o nó atual como parâmetro. Por exemplo:

// Travessia em ordem
function emOrdem($no) {
  if ($no != null) {
    emOrdem($no->esquerdo); // visita o filho esquerdo
    echo $no->valor . " "; // visita o nó atual
    emOrdem($no->direito); // visita o filho direito
  }
}

// Travessia pré-ordem
function preOrdem($no) {
  if ($no != null) {
    echo $no->valor . " "; // visita o nó atual
    preOrdem($no->esquerdo); // visita o filho esquerdo
    preOrdem($no->direito); // visita o filho direito
  }
}

// Travessia pós-ordem
function posOrdem($no) {
  if ($no != null) {
    posOrdem($no->esquerdo); // visita o filho esquerdo
    posOrdem($no->direito); // visita o filho direito
    echo $no->valor . " "; // visita o nó atual
  }
}

Árvore AVL

Uma árvore AVL é uma árvore binária que se mantém balanceada, ou seja, que a diferença de altura entre as subárvores esquerda e direita de cada nó é no máximo um. É usada para garantir que as operações de busca, inserção e remoção tenham complexidade logarítmica. Para implementar uma árvore AVL em PHP, precisamos fazer rotações nos nós quando a árvore ficar desbalanceada. Por exemplo, para criar a seguinte árvore AVL:

    10
   /  \
  5    15
 / \   / \
3   7 12 20

Podemos fazer:

$raiz = new No(10);
$raiz->esquerdo = new No(5);
$raiz->direito = new No(15);
$raiz->esquerdo->esquerdo = new No(3);
$raiz->esquerdo->direito = new No(7);
$raiz->direito->esquerdo = new No(12);
$raiz->direito->direito = new No(20);

// Se inserirmos o nó 25 na subárvore direita, a árvore ficará desbalanceada:
$raiz->direito->direito->direito = new No(25);

// Para balancear a árvore, precisamos fazer uma rotação à esquerda no nó 15:
$novoNo = $raiz->direito; // nó 15
$temp = $novoNo->esquerdo; // nó 12
$novoNo->esquerdo = $raiz; // nó 10
$raiz->direito = $temp; // nó 12
$raiz = $novoNo; // nó 15

// Agora a árvore está balanceada novamente:
/*
     15
    /  \
   10   20
  / \     \
 5   12    25
/ \
3   7
*/

Conclusão

Neste post, vimos como usar árvores em PHP e aprendemos sobre alguns tipos de árvores, como árvore binária, árvore AVL. Vimos também como implementar essas árvores em PHP e como fazer operações básicas nelas. Espero que você tenha gostado e aprendido algo novo.

Árvores são estruturas de dados muito poderosas e versáteis, que podem ser usadas para resolver diversos problemas. Elas permitem organizar e acessar os dados de forma eficiente e hierárquica. Existem muitos outros tipos de árvores que não abordamos neste post, como árvores trie, árvores de segmento, árvores de sufixo, entre outras. Se você quiser saber mais sobre elas, recomendo que pesquise na internet ou em livros de algoritmos e estruturas de dados.