Что такое balanced tree?

Balanced tree — дерево, где высота поддеревьев отличается не более чем на 1 (или по другому критерию). AVL-дерево, Red-Black дерево, B-tree — примеры. Гарантируют O(log n) для всех операций, в отличие от обычного BST, которое может выродиться в список. Red-Black дерево используется внутри map в C++ и TreeMap в Java. B-tree — основа индексов в PostgreSQL и других БД. В Go стандартной реализации нет, но есть сторонние библиотеки (google/btree).