Binary search trees
Hello, I am learning data structures and reading up on binary search trees, and I am having some issues understanding some parts of it.
Every example I come across is only using 1 piece of data, so adding and searching that data is simple. But I am wondering what if you wanted to store more information in one of these nodes (or can it only be one piece of data). For instance if i wanted to create a phonebook app, that used a binary search tree, and I wanted to store information of each persons name, phone number and address, and i also wanted to be able to search based on any of those, is that possible.
The way I have these trees working in my head is, the name would be stored as the main piece of data, so the trees are organised based on that. So if I wanted to then search for a phone number or address, it would not be in order of number or address, and therefore would fail to find the information.
I figure I am misunderstanding something here with these trees, but I just cant figure them out, and like i said, every video or tutorial on them all just uses 1 piece of detail, which is a number
Every example I come across is only using 1 piece of data, so adding and searching that data is simple. But I am wondering what if you wanted to store more information in one of these nodes (or can it only be one piece of data). For instance if i wanted to create a phonebook app, that used a binary search tree, and I wanted to store information of each persons name, phone number and address, and i also wanted to be able to search based on any of those, is that possible.
The way I have these trees working in my head is, the name would be stored as the main piece of data, so the trees are organised based on that. So if I wanted to then search for a phone number or address, it would not be in order of number or address, and therefore would fail to find the information.
I figure I am misunderstanding something here with these trees, but I just cant figure them out, and like i said, every video or tutorial on them all just uses 1 piece of detail, which is a number
its just like any other container: its sorted by one thing and can use the sorting of that thing to find it quickly. Anything else requires a slower search … you touch every item to see if that one is 'it' when it isn't sorted. Just like an array: unsorted array, check every item, sorted array, binary search, its the exact same thing!
that said, there are loads of ways to deal with this problem so you can find things efficiently by other keys. You could hash by each search key into multiple tables of pointers to the actual items, storing each record once but pointers to it many times. In fact, due to the double pointers of a balanced tree, you can search 2 keys on an array this way at little extra cost over a tree. Depending on exactly what you want to allow searches on, you can solve the problem.
Databases have multiple search keys that are fast, and if you ignore that and search something else, they return the results MUCH slower than if you had used a key, as a real world example. Study of how to key the data is a big deal in the design of a big system.
what I am saying is: you have it right, but the problem can be solved if you need to search fast on multiple keys.
that said, there are loads of ways to deal with this problem so you can find things efficiently by other keys. You could hash by each search key into multiple tables of pointers to the actual items, storing each record once but pointers to it many times. In fact, due to the double pointers of a balanced tree, you can search 2 keys on an array this way at little extra cost over a tree. Depending on exactly what you want to allow searches on, you can solve the problem.
Databases have multiple search keys that are fast, and if you ignore that and search something else, they return the results MUCH slower than if you had used a key, as a real world example. Study of how to key the data is a big deal in the design of a big system.
what I am saying is: you have it right, but the problem can be solved if you need to search fast on multiple keys.
Last edited on
Topic archived. No new replies allowed.