Thanks to their simplicity, binary search trees are beautifully efficient. In fact, the entire tree implementation for this section was done in fewer than 90 lines of Rust code, with functions of about 10 lines each.
A binary tree's efficiency allows for recursion to be used a lot, which typically results in functions that are easier to understand compared to their iterative counterparts. In the ideal case, that is, when a tree is perfectly balanced, a function only has to process log2(n) nodes (n being the total number of nodes)—19 in a tree of 1,000,000 elements!
Unbalanced trees will decrease performance significantly and they are easily created by accident. The most unbalanced tree is created by inserting values that are already sorted, creating a very large difference in search performance:
test tests::bench_sorted_insert_bst_find ... bench: 16,376 ns/iter (+/- 6,525)
test tests::bench_unsorted_insert_bst_find ... bench: 398 ns/iter (+/- 182)
These results reflect...
