The Complete Rust Programming Reference Guide

Wrap up

Red-black trees are great self-balancing binary trees, similar to AVL (short for Adelson-Velsky and Landis) trees. Both appeared around the same time, yet AVL trees are considered to be superior thanks to a lower height difference between the branches. Regardless of which tree structure is used, both are significantly faster than their less complex sibling, the binary search tree. Benchmarks using sorted data on insert (100,000 elements in this case) show how significant the difference between a balanced and unbalanced tree is:

test tests::bench_sorted_insert_bst_find ... bench: 370,185 ns/iter (+/- 265,997)test tests::bench_sorted_insert_rbt_find ... bench: 900 ns/iter (+/- 423)

Another variation of a balanced tree is the 2-3-4 tree, ...