Menu
Is there a reason why I don't see binary search trees used much in Ruby?
Is there an equivalent data structure or class that people typically use instead?
I'm not trying to solve a specific problem; just trying to learn more about the language.
thanks!
618
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. --Wikipedia. All trees start with a root, so does the Binary tree. For the above example, the top node with a 5 is the root.
Yes, it is. Since the elements of the BST satisfy a total preorder, an in-order traversal of the BST must produce those elements in order (Ex: prove it). It is equivalent to state that if we had stored a BST's keys, by an in-order traversal, in an array, the array would be sorted.
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side.
Binary search trees are a relatively low-level implementation detail, usually for a map/table abstract data type. In Ruby, if you want a map/table, you just use a Hash. If you have a problem that specifically needs binary search trees, there's also a good chance a Ruby implementation will be too slow to be useful.
186
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
