Читаю про бинарные деревья поиска, и написано, что при добавлении элемента он сразу должен добавляться в нужное место.. .
Для чего тогда в WinAPI нужна функция для балансировки дерева RtlSplay, если дерево изначально создаётся таким, каким и должно быть?
В общем случае бинарное дерево не является сбалансированным. Именно поэтому балансировка дерева, как достаточно затратная операция, вынесена в отдельный метод. Это позволяет перебалансировать дерево не каждый раз после добавления/удаления элементов, а динамически, например, во время простоя. А если нам не нужно сбалансированное дерево, то мы его и не балансируем.
Дополню Владимира Кольца: Есть специальные деревья, которые при добавлении сами балансируются, но там используется довольно хитрый алгоритм, который понижает скорость добавления элементов. Поэтому иногда имеет смысл сначала добавить все элементы, а потом сбалансировать дерево.
⇢