Идеально сбалансированные деревья - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Как построить идеально сбалансированное дерево?

• взять одну вершину в качестве корня.
• построить левое поддерево с nl = n DIV 2 вершинами тем же способом.
• построить правое поддерево с nr = n-nl-1 вершинами тем же способом.

void createBalancedTree(Node*& node, int n, ifstream& f) 
{
	if (n > 0)
	{
		int elem;
		f >> elem;
		node = new Node(elem);
		createBalancedTree(node->left, n / 2, f);
		createBalancedTree(node->right, n - (n/2) - 1, f);
		
	}
}

Идеально сбалансированные деревья изобретены для сокращения времени работы вычислительных алгоритмов, связанных с необходимостью частого прохода по ветвям дерева (напомним, что ветвь - это путь от корня дерева до листа). Одним из примеров подобного рода алгоритмов является поиск информации в дереве. Для поиска придется перебрать не более log2n вершин, где n - число вершин в дереве. Одно "но": при формировании идеально сбалансированного дерева ключи необходимо вводить в отсортированном по возрастанию (по убыванию) виде.

Поэтому второй способ построения идеально сбалансированного дерева - через отсортированный по возрастанию массив, начиная выстраивать дерево с центрального элемента.