Hands-On Data Structures and Algorithms with Rust

Better IoT device management

The problem that our users face is clear: if a binary search tree encounters sorted data (such as incremental IDs), it can only ever append to one side, creating an unbalanced tree. A red-black tree is able to handle this at the cost of more operations being executed during insert (such as rotating subtrees), which is acceptable for the users.

This tree has similar nodes to the binary search tree, with the addition of a color field and a parent field, the latter of which triggers a wider change compared to the binary search tree. Thanks to the pointer back, the tree nodes cannot exclusively own the pointers to the children and parent (because, who owns this value, the parent or the child?), which requires a well-known ...