Доказательство глубины сбалансированного дерева поиска
-
18-09-2019 - |
Вопрос
Если T — сбалансированное BST с n элементами, L — левым поддеревом, а R — правым, как я могу доказать, что его глубина меньше или равна 2log(n) + 1?
У меня есть доказательство по индукции, но я его не понимаю.
(Я понимаю, что stackoverflow в основном ориентирован на программирование, но я нашел несколько вопросов о деревьях двоичного поиска и решил попробовать, надеюсь, я не делаю что-то плохое.:))
Решение
По определению «сбалансированного», глубина каждого левого и правого поддерева одного и того же узла отличается не более чем на единицу.«Глубина» обычно определяется как «количество шагов наибольшего пути от корня дерева до листа», поэтому, например, 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)
и без завершения «а тем более», и доказательство остается в силе.
Другие советы
Ваш ответ верен: если сбалансированное двоичное дерево завершено, количество элементов в правом и левом поддереве может составлять (n-1)/2, но если оно не полное, количество элементов не обязательно должно быть (n-1)/2, как последний уровень может иметь разные элементы