Practical uses for Binary Search Tree

Good morning folks,
I have searched for this answer online and can't find it. I am just trying to get an idea of the real world applications where Binary Search Trees might be used. I did a paper on it and stated that it was used in many applications where quick searching was required and was told that they wanted more specifics. Paper is graded and done, now just doing the after research on my own to find out some real world examples of where it might be used.

Any information would be appreciated.

Thanks
Wally

If you know C++, investigate the typical data structures used to implement std::set and std::map, and then the various uses for std::set and std::map.

Quote:

---

Originally Posted by wfsteadman

I did a paper on it and stated that it was used in many applications where quick searching was required and was told that they wanted more specifics. Paper is graded and done, now just doing the after research on my own to find out some real world examples of where it might be used.

---

I don't think they wanted specfic examples of applications using binary search trees. It's because close to every application use them in one way or another. Often in modified form and often behind the scene in some standard library or 3'rd party library. It's very seldom you need to implement a binary search tree yourself. I can't recall I've ever done it for real, only toying with it in education.

What they probably wanted was for you to be more specific about what you mean by "quick searching". The easiest way would've been to supply a table where the key properties and characteristics of the most common basic data structures such as array, linked list, hash table and binary tree are compared and contrasted.

And not only average performances. For example if a binary tree isn't balanced and items are entered in sorted order then it essentially becomes a linked list. Then the expected fast O(log N) search time degrades to the worst case O(N) and isn't faster than a linear search anymore.