Высота сбалансированного дерева двоичного поиска

Question

Почему максимальное время достижения элемента в сбалансированном двоичном поиске - это log n, когда на самом деле идеально сбалансированное дерево имеет 1, 3, 7, 15 элементов (то есть 1 меньше, чем кратное 2). Ответ, приведенный здесь Why is the height of a balanced binary search tree log(n)? (Proof), скажем, предположим, что у нас есть 2^N узлов (кратное 2)

Но если взять журнал этих нечетных чисел, мы не получим круглого номера для высоты!

Вопрос:

ли это на самом деле журнал (п + 1), но затем откинуть +1, так как это незначительно при огромном п?

Answer 1

Это самая низкая верхняя граница, что означает, что она достигнута для некоторого n. Обратите внимание, что тривиальное дерево с корнем имеет высоту, определенную как 0, а не 1, как вы, вероятно, предполагали. Например. идеально сбалансированное дерево с тремя элементами имеет высоту 1, а дерево с 4 элементами имеет высоту 2, которая является log (4).

Answer 2

Константы удалены из O(..) обозначение, если только они не имеют значения. В вашем примере добавление + 1 не влияет на время выполнения, поэтому мы будем говорить о O(log n) вместо O(log n + 1).

В любом случае поиск элемента в сбалансированном двоичном дереве равен O(log n), потому что на каждом шаге вы уменьшаете вдвое размер дерева, который вам еще нужно выполнить. Эта большая O-нотация выражает время выполнения алгоритма, так как n растет, он не предназначен для вычисления количества операций, которые вы будете выполнять (поскольку могут быть задействованы некоторые дополнительные операции и т. Д.).

Обратите внимание, что вопрос, который вы связаны переговоры о 2^Nлистовых узлов так бинарное дерево с 2^2 = 4 листовыми узлами будет иметь 7 общих узлов. Значение N в этом другом вопросе не совпадает с n в этом вопросе.