  We develop the first fully dynamic algorithm that maintains a decision tree
over an arbitrary sequence of insertions and deletions of labeled examples.
Given $\epsilon > 0$ our algorithm guarantees that, at every point in time,
every node of the decision tree uses a split with Gini gain within an additive
$\epsilon$ of the optimum. For real-valued features the algorithm has an
amortized running time per insertion/deletion of $O\big(\frac{d \log^3
n}{\epsilon^2}\big)$, which improves to $O\big(\frac{d \log^2
n}{\epsilon}\big)$ for binary or categorical features, while it uses space $O(n
d)$, where $n$ is the maximum number of examples at any point in time and $d$
is the number of features. Our algorithm is nearly optimal, as we show that any
algorithm with similar guarantees uses amortized running time $\Omega(d)$ and
space $\tilde{\Omega} (n d)$. We complement our theoretical results with an
extensive experimental evaluation on real-world data, showing the effectiveness
of our algorithm.
