Каково количество узлов на определенном уровне в сбалансированном бинарном дереве поиска?

Question

Мне задали этот вопрос в интервью на экране телефона, и я не смог на него ответить.Например, в BST я знаю, что максимальное количество узлов дается 2 ^ h (при условии, что корневой узел на высоте = 0)

Я хотел спросить, есть ли аналогичный математический результат длясбалансированное двоичное дерево поиска (для AVL, красные черные деревья?), то есть количество узлов на определенном уровне k.

Спасибо!

Answer 1

Сбалансированное двоичное дерево начинается с одного узла, который имеет двух потомков.У каждого из них снова есть два потомка.Таким образом, будет 1, 2, 4, 8 и т. Д. Узлов на уровень.

В качестве формулы вы можете использовать 2^(level-1).Последняя строка может быть не полностью полной, поэтому в ней может быть меньше элементов.

Поскольку этап балансировки дорогостоящий, реализации обычно не перебалансируются после каждой мутации дерева.Они скорее применят эвристику, чтобы выяснить, когда перебалансировка будет наиболее целесообразной.Таким образом, на практике уровни могут иметь меньше узлов, чем если бы дерево было идеально сбалансировано, и могут быть дополнительные уровни от узлов, вставляемых в неправильных местах.