Доказательство глубины сбалансированного дерева поиска

Question

Если T — сбалансированное BST с n элементами, L — левым поддеревом, а R — правым, как я могу доказать, что его глубина меньше или равна 2log(n) + 1?

У меня есть доказательство по индукции, но я его не понимаю.

(Я понимаю, что stackoverflow в основном ориентирован на программирование, но я нашел несколько вопросов о деревьях двоичного поиска и решил попробовать, надеюсь, я не делаю что-то плохое.:))

Answer 1

По определению «сбалансированного», глубина каждого левого и правого поддерева одного и того же узла отличается не более чем на единицу.«Глубина» обычно определяется как «количество шагов наибольшего пути от корня дерева до листа», поэтому, например, BST с одним корнем и двумя листьями (три элемента в единственном способе их расположения в сбалансированном BST) — это говорят, что он имеет глубину один (похоже, вы используете немного другое определение, которое дало бы ему глубину два?), как и один с одним корнем и одним листом (независимо от того, является ли этот лист левым или правым поддеревом корня, не имеет значения), в то время как тот, у которого есть только корень, который также является листом (одиночный элемент), будет иметь глубину 0.(БСТ с нулевыми элементами не существует).

Таким образом, для n <= 3 элементов, называя D(n) глубину дерева, определенную выше, ясно 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), КЭД.

Если n даже если вы выполняете те же действия, что и log(n) вместо log(n-1) и без завершения «а тем более», и доказательство остается в силе.

Answer 2

Ваш ответ верен: если сбалансированное двоичное дерево завершено, количество элементов в правом и левом поддереве может составлять (n-1)/2, но если оно не полное, количество элементов не обязательно должно быть (n-1)/2, как последний уровень может иметь разные элементы