I understand that a binary search tree is a graph with rules and how it’s used in coding but relaying it in math terms is confusing me
In: 0
Imagine doing a search and picking one item from a group. Let’s say that that item isn’t a match. Because it’s not a match, you now know that half of the items in that group also don’t match (because the group is sorted).
So, you start a search again but on the other half. Pick an item, does it match? If yes, great. If not, you can now eliminate half of the items in *that* group. Since you eliminated half of the group you originally started with and half of the sub-group, you’re now down to 1/4 of the original group.
Each search reduces the possibilities by half, making a binary tree search very efficient.
Do you want ELI5 or graph theoretic terms?
If you want graph theory, best to go to r/askmath ; but in simple terms it is a tree where each parent has at most two children, and the children are identified as left child and right child. The left child’s value is always less than or equal to the parent’s value, which is always less than or equal to the right child’s value.
That’s the full graph theoretic description – from there you can start to form efficient algorithms for search, hence the “search” in the name.
For ELI5: imagine you have a list of items that’s been prearranged by some value ordering. How would you find an item of a particular desired value? You might start by looking somewhere in the middle of the list – if it’s greater than your value, then you know it’s somewhere prior to the place you looked, and you’d next try somewhere near the middle of that section, etc.
What I have described is a binary search of a sorted list. If you were to connect the possible paths of searches that may result from any particular desired value with an edge, the resulting shape is a binary search tree. ie a binary search tree encodes this algorithm in terms of what “somewhere near the middle” means for any particular section.
It’s a graph where there is exactly one path between any pair of nodes and all nodes have a degree of three or less.
Latest Answers