Lab notes #010 4th time's the charm to rewrite append
Most of this week has been spent rewriting `append()`. This stemmed from mostly following the pseudocode from the L'Orange paper too closely. Excited about ChatGPT, I used it to convert the pseudocode to Rust code and tried to go from there. However, in the end, I found that it was much better to just understand the intent of the pseudocode and rewrite it in Rust given its nature.
- Most of the problem stemmed from the pseudocode from C or C++, where the new branch as a result
append()is built from the root on down. This is more problematic because you end up having to create nodes and then mutate them. Given that I'm a new Rust programmer, that invokes a lot of problems from the borrow checker that I'm not always quite sure how to solve.
- The other issue is that you need to do a look-ahead to find the deepest vacant rightmost node to do an insertion. And for us to find that node first, we first have to do a single traversal down the right side to find that node.
- To build from the bottom up, the nodes have to be first traversed and then processed in reverse order. In order to do that, I tried writing an iterator, and a traversal method that yielded a closure. It turns out it's hard to write a recursive function with a closure that mutates its closure. At the end of the day, I opted for an iterative solution with a stack. The traversal down filled the stack, and then the closure is called as the stack is popped.
At the end of the day, the pre-traversal isn't as big of a deal since the height of the tree is limited to about 7 levels in an RRBT.