Binary Search Trees are a convenient structure for storing data because search, access, insertion, and deletion operations have an average time complexity of O(log(n)) with a worst case of O(n). It‘s also useful for sorting because insertion into a BST is inherently sorted!
We’re covering trees in my DSA class this week and I happen to be learning Rust, so I thought I’d take the opportunity to explore the structure in my new favorite language!
Let’s walk through this step-by-step:
We’re first declaring a public struct
BST whose fields can hold a generic type
T. We want to limit
T to types that implement primarily the
Debug traits, optionally
Ord allows ordinal value comparisons,
Debug allows debug-formatted printing, and
Copy is an optional trait that will allow us to unwrap
Options for other special features (like GraphViz integration).
Each node in our BST can hold a value, a left node, and a right node. We’ll wrap the left and right children in pointers to other nodes,
Box<BST<T>> , and wrap them again in an
Option because a node doesn’t necessarily have a child. We can use this
Option to ensure we cover all possible cases later on.
When creating an instance of our BST, we might take two paths: a blank instance, for example creating an empty BST into which nodes can be inserted, or creating a node based on a value.
from() both create a new instance of our BST with these distinct purposes in mind.
Inserting things into a BST is where things might seem to get a little hairy, so let’s walk through the process.
- Traverse the tree by comparing the new value to each node you reach. If the new value is less than (or equal to) the existing node’s value, set your target for insertion to the current node’s left child. If the new value is greater than the existing node’s value, set your target to the right.
- If you find an existing node in your insertion target, just repeat the
insert()process for that node.
- If you find an empty space in your insertion target, create a node
from()the new value and set your target space to be an
Boxto that node.
Ordered insertion gives us the ability to find the minimum and maximum values extremely easily! Again using recursion, we can just traverse the left/right children (less than/greater than respectively) until we can’t anymore. It’s like a gift for being responsible with our insertion!
Recursive searching can also be a hairy thing to wrap your mind around, but Rust’s pattern matching goes a long way towards clearing things up! We start by making sure our current node has a value at all. If it doesn’t, we’ve reached the end of the line and can return
false. If we find a value there, we can match again on a comparison between the target and the value in
&self, here aliased as
key. If this comparison comes out to
Equal, we’ve found the element! The rest should feel familiar; if we’re looking for a value less than the current node, we just
search() the left branch. Greater,
Binary search trees have some incredibly useful qualities that are only bolstered by Rust’s guarantees towards memory safety and efficiency. Its robust pattern matching also helps to make decision trees both exhaustive and more human-readable!