Binary search trees (BSTs) of various sorts and their variations are widely used data structures today, so they are hardly a "historical note". For example, both the .NET Framework and the Java Standard Library provide a tree-based implementation of a dictionary. A red-black tree no less in the latter case.
One of the reasons for this is that tree-based implementations more easily provide desirable functionality. It's not a surprise that the .NET Dictionary
type is a hash table, but the SortedDictionary
type is a tree. Providing values in order or doing range queries is something that is awkward with hash tables. Making hash tables persistent (as in allowing old "versions" to be used, not as in on-disk) is also fairly awkward, but it is much more straightforward for trees. Most functional mapping data structures are based on trees, though usually quite a bit fancier than red-black trees and possibly also incorporating hashing as in hash array mapped tries (HAMTs).
Even if you don't need those extra features, sometimes "expected" isn't enough. Those "expectations" are based on assumptions that an adversary can exploit. It's not necessary to use trees to avoid the mentioned issue, but sometimes more predictable behavior than "expected" and "amortized" is necessary.
Finally, many data structures incorporate BSTs or at least ideas from BSTs. For example, most databases use variations on B-trees which are basically "non-binary" search trees. As a pedagogical aspect, proving things about red-black trees, say, is likely an easier exercise than proving things about PATRICIA trees or HAMTs but still exercises many of the concepts that are being taught.