The Complete Rust Programming Reference Guide

Summary

This chapter went deep into trees, starting off with the simplest form: the binary search tree. This tree prepares the inserted data for search by creating a left and a right branch which hold smaller or greater values. A search algorithm can therefore just pick the direction based on the current node and the value coming in, thereby skipping a majority of the other nodes.

The regular binary search tree has a major drawback, however: it can become unbalanced. Red-black trees provide a solution for that: by rotating subtrees, a balanced tree structure is maintained and search performance is guaranteed.

Heaps are a more exotic use of the tree structure. With their primary use as a priority queue, they efficiently produce the lowest ...