We introduce a new method to learn an adaptive dictionary structure suitable for efficient coding of sparse representations. The method is validated in a context of satellite image compression. The dictionary structure adapts itself during the learning to the training data and can be seen as a tree structure whose branches are progressively pruned depending on their usage rate and merged into a single branch. This adaptive structure allows a fast search for the atoms and an efficient coding of their indices. It is also scalable in sparsity, meaning that once learned, the structure can be used for several sparsity values. We show experimentally that this adaptive structure offers better rate-distortion performances than the "flat" K-SVD dictionary, a dictionary structured in one branch, and the tree-structured K-SVD dictionary (called Tree K-SVD).