По определению " сбалансированный ", глубины каждого левого и правого поддеревьев одного и того же узла отличаются не более чем на один. «Глубина» обычно определяется как «число шагов от самой длинной ходьбы от корня дерева до листа», так например, BST с одним корнем и двумя листьями (три элемента, в единственном способе их размещения в сбалансированном BST) сказал, что имеет глубину 1 (похоже, вы используете немного другое определение, которое даст ему глубину два?), как и один с одним корнем и одним листом (независимо от того, является ли этот лист левым или правым поддеревом корня не имеет значения), в то время как один с одним корнем, который также является листом (один элемент), будет иметь глубину 0. (Нет BST с нулевыми элементами).
Таким образом, для п < = 3 элементы, требующие D (п) глубина дерева, как определено выше, очевидно, D(n) < log(n) + 1 (с log значением базового 2 логарифма) путем осмотра, так как 1 = D(2) < log(2) + 1 = 2 (а также 1 = D(3), для которых правая часть неравенства , log(3) + 1, фактически > 2), и 0 = D(1) < log(1) + 1 = 1 - это дает нам индукционную базу.
Для завершения доказательства по индукции мы должны показать, что если D(k) < log(k) + 1 для всех k < n, то также следует, что D(n) < log(n) + 1.
Если n нечетное, то четкое левое и правое поддерево имеют (n-1)/2 элементов каждый, а дерево имеет глубину 1 больше, чем поддеревья; но затем D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (по индуктивному предположению) = 1 + log(n-1) (с log((n-1)/2) = log(n-1) - 1) и, следовательно, более < 1 + log(n), QED.
Если вы используете только n, выполните следующие действия: log(n) вместо log(n-1) и без «фортификационного» финиша.
Это домашнее задание? –
Нет, это просто на моих заметках. – 2009-11-08 01:13:43