We investigate the problem of computing in the presence of faults
that may arbitrarily (i.e., adversarially) corrupt memory locations.
In the faulty memory model, any memory cell can get corrupted at any
time, and corrupted cells cannot be distinguished from uncorrupted
ones. An upper bound $\delta$ on the number of corruptions and $O(1)$
reliable memory cells are provided. In this model, we focus on the
design of resilient dictionaries, i.e., dictionaries which are able
to operate correctly (at least) on the set of uncorrupted keys. We
first present a simple resilient dynamic search tree, based on
random sampling, with $O(\log n + \delta)$ expected amortized cost
per operation, and $O(n)$ space complexity. We then propose an
optimal deterministic static dictionary supporting searches in
$\Theta(\log n+\delta)$ time in the worst case, and we show how to use
it in a dynamic setting in order to support updates in $O(\log
n+\delta)$ amortized time. Our dynamic dictionary also supports range
queries in $O(\log n+\delta+t)$ worst case time, where $t$ is the size
of the output. Finally, we show that every resilient search tree
(with some reasonable properties) must take~$\Omega(\log n +
\delta)$ worst-case time per search.