PHPTree, a fast tree implementation
  7 minutes  1404 wordsHopefully for most of us, holidays are here. A special time for resting and enjoy quality time with the family, but also for thinking.
Even if I’m not attached to any religion, doing a Christmas tree is a kind of tradition… cats really loves it :)
While decorating the tree, it got me thinking about tree based data structure. I used to play with trees into a previous project with Neo4J and I remember that I loved it.
And even if I have vague souvenirs about trees and data structure from university, I started to reinvestigate into graphs and trees.
A bit of theory
The term “tree” was coined in 1857 by the British mathematician Arthur Cayley.
In mathematics, and, more specifically, in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. Every acyclic connected graph is a tree, and vice versa.
Just like in Nature, there are different types of trees for data structure and the various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees.
A rooted tree may be directed either making all its edges point away from the rootn (in which case it is called an arborescence, branching, or outtree), when its edges point towards the root (in which case it is called an antiarborescence or intree).
A rooted tree itself has been defined as a directed graph.
I’m just giving here a small introduction, you can find more details on this on Wikipedia.
Examples
Here’s a very simple data representation using a tree.
12 nodes, degree 11 (each node has maximum 11 children], 11 leaves and height is 1.
This tree is full, every nodes other than the leaves has the same number of children.
12 nodes, degree 3, 8 leaves, height is 2.
This tree is complete, every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
There are many configuration possible for storing data in a tree, here’s another one.
This tree is a degenerate (or pathological) tree is where each parent node has only one child node.
As you can see, graphs have its own vocabulary and classification.
A tree can be summarized with one simple definition (from this amazing article)
A tree is a collection of entities called nodes. Nodes are connected by edges. Each node may or may not contains some data, and it may or may not have a child node. The first node of the tree, usually at the top, is called the root node.
Tree traversal
In computer theory and algorithms, one of the most important facet of trees is the way we read them. As a tree is a 2 dimensional data structure, we cannot read it from the top to the bottom like we would do it in a simple list, data are organized hierarchically.
That said, we must find strict ways to “traverse” them.
There are 4 well known tree traversal algorithms:
 In Order (Depth first)
 Pre Order (Depth first)
 Post Order (Depth first)
 Breadth first (Breadth first)
Usually those traversal algorithms are made for binary trees (2ary trees), trees having maximum 2 children per node.
Find all the details and more on Wikipedia.
About the library
The purpose of this post is not about trees theory but about a library I’ve been working on called: PHPTree.
It allows you to manipulate trees, to export and import them.
PHPTree is gentle with memory thanks to PHP Iterator(Yield, ArrayObject), I tried to use them as much as possible.
Tree types
Currently, the library provides 5 different types of objects, maybe some other trees will be implemented later, depending on my availability.

Node: A simple base class that can be added to another one or be used as a parent for other children.

Nary node: It extends the Node class and allows you to cap the number of children a node can have. A Kary or Nary tree is tree in which each node has no more than N children. This tree does the heavy lifting for you when adding nodes.

Value node: extends the Nary node and allows you to attach a value to the node.

KeyValue node: extends the Value node and allows you to attach a key and a value to the node.

Trie node: extends the KeyValue node, a Trie tree node. (see example)
Tree traversal algorithms
PHPTree also implements the 4 well known tree traversal algorithms with some extra.
Many of these algorithms are made to work with 2ary trees (binary trees), in PHPTree, they are working for all kind of trees.
I think this is something new, I was not able to find any equivalent on the internet.
Example with a binary tree
Let this binary tree (2ary tree):
be traversed with the InOrder algorithm, the result would be:
O, G, P, C, Q, H, R, A, S, I, T, D, U, J, V, root, W, K, X, E, Y, L, Z, B, M, F, N
Example with another tree
Let this tree (4ary tree):
be traversed with the InOrder algorithm, the result would be:
U, V, E, W, X, Y, F, Z, A, G, H, I, J, B, K, L, root, M, N, C, O, P, Q, R, D, S, T
The InOrder tree traversal is usually made for binary trees, PHPTree has standardized the algorithm and it can work with any type of trees.
Tree exporters
PHPTree gives you the opportunity to export trees in multiple formats:
 To text
 To ascii (just for fun)
 To PHP array
 To Graph
Here’s an example of how this graph is exported:
To text
[PHPTree [is [fast [to] [manipulate]] [and [trees] [data]]] [a [fun [structure]] [library]]]
To ascii
├─ PHPTree
└─┐
├─┐
│ ├─ is
│ └─┐
│ ├─┐
│ │ ├─ fast
│ │ └─┐
│ │ ├─┐
│ │ │ └─ to
│ │ └─┐
│ │ └─ manipulate
│ └─┐
│ ├─ and
│ └─┐
│ ├─┐
│ │ └─ trees
│ └─┐
│ └─ data
└─┐
├─ a
└─┐
├─┐
│ ├─ fun
│ └─┐
│ └─┐
│ └─ structure
└─┐
└─ library
To PHP array
<?php
$tree = [
'value' => 'PHPTree',
'children' => [
0 => [
'value' => 'is',
'children' => [
0 => [
'value' => 'fast',
'children' => [
0 => [
'value' => 'to',
],
1 => [
'value' => 'manipulate',
],
],
],
1 => [
'value' => 'and',
'children' => [
0 => [
'value' => 'trees',
],
1 => [
'value' => 'data',
],
],
],
],
],
1 => [
'value' => 'a',
'children' => [
0 => [
'value' => 'fun',
'children' => [
0 => [
'value' => 'structure',
],
],
],
1 => [
'value' => 'library',
],
],
],
],
];
To Graph
Graph is a class from the package graphp/graph of Christian Lück, so I won’t be able to show it here.
However, this is thanks to it that we can export trees into images or dot files thanks to Graphviz and it’s PHP package graphp/graphviz.
Tree importers
PHPTree also provides 2 importers:
 From text
 From PHP array
The text exporter and importer can be very useful to store/retrieve a tree into/from a database.
Tree modifiers
A modifier is an object that modify a tree and return a new modified tree.
Let this tree:
Be modified with the Reverse modifier:
Code examples
I posted on gist the code that I used to generate the trees in this post, feel free to test them as well.
Just for fun, I also made 2 trees with 10000 nodes to visually explain the difference between a tree of degree 2 and 3:
Conclusion
Building this library helped me understand in depth the advantage of using Iterators and Yield in my projects.
Besides the fact that doing this library was really fun, some parts were extremely hard, especially the tree traversal algorithms.
Let me know if you’re going to use it and how! Feedback is very welcome.