Самобалансівні дерева: AVL і червоно-чорне дерево

Коротко: Дерева пошуку, що перебудовуються після вставлення й видалення, щоб не вироджуватися в довгий ланцюжок і щоб операції лишалися швидкими.

Докладніше: Двійкове дерево пошуку знаходить значення за O(log n), якщо воно збалансоване. Але якщо вставляти відсортовані дані (1, 2, 3, 4, …), виходить довгий «ланцюжок» із витратами O(n). Самобалансівні дерева виявляють такий дисбаланс і відновлюють баланс обертаннями.