Balanced binary tree versus hash table is an implementation choice for the associative array abstract data type. Similarly, growable array versus linked list are implementation choices for the list abstract data type.

I don't buy that balanced binary trees are "too computer sciencey for most people's taste" as an argument against not have them as implementations of native types in Python. Designing a good hash table is equally as subtle in terms of both the theory and the implementation itself. But those details are not exposed through the interface.