Binary tree - why is it needed and how is it obtained?

Question

Data Structures

Hello!
Explain, please, that in general any data structure is not a data type. How are data structures formed?
Are they somehow "wired" under the hood in the interpreters of programming languages? I'm just completely confused.

For example, a quote from Wikipedia:

The binary search tree is used to build more abstract structures such as sets, multisets, associative arrays.

But, isn't an associative array a dictionary in the case, for example, with the Python language? Isn't a dictionary a hash table data structure? I have already read a bunch of articles, but everywhere it only explains what trees are, but where they “appear” so to speak is not said anywhere.

I'm sorry, I know it's a dumb question. I honestly read, for example, "Groaming Algorithms", but there, too, I did not find anything about where the data structures come from.

Many thanks in advance for your help!

Answer 1

First, understand how linked lists are implemented. Here is a binary tree - it's almost the same, only each element has 2 links and not one. Just a way of organizing data that has some useful properties.
Everything inside is implemented on pointers, arrays and structures (stupidly a group of different variables combined into one type).
A dictionary in python, also known as an associative array, is indeed implemented on the basis of a hash table. Implemented inside the Python interpreter. This is another data structure based on arrays and lists (which are implemented on pointers).
But an associative array can also be implemented with binary search trees. For example, the set structure in C++ is implemented by a tree. Such an associative array is asymptotically slower (logarithm of operations instead of a constant for searching/inserting/deleting). But it has an important property - the elements are ordered there. You can find the minimum key, go around all the keys in ascending order, calculate something on the segment of the keys. Plus, you don't need to come up with a good hash. In hash tables, if the hash is bad, you can get O(n) operations. Or it may not lead and there will be a lot of collisions even for a good hash. In binary search trees (most) the worst case per logarithm is guaranteed. In some tasks, it is better to use this structure than a hash table.
Plus, there are all sorts of other tree-based data structures: segment tree, binary heap, boron.