Итак, я изучал сбалансированное двоичное дерево поиска.Определение сбалансированного дерева двоичного поиска
Я гугле, и это то, что я нашел:
бинарное дерево, в котором глубина двух поддеревьев каждого узла отличаются на 1 или меньше (из википедии)
Может 't мы просто определяем сбалансированное двоичное дерево как дерево с высотой не более, чем ceil (log (n + 1)/log 2)?
И, кажется, из этого ответа Is Binary Search tree balanced?, вопросник, похоже, уже просил очень то же самое, но принятый ответ отвергает эту идею, подавая пример дерева фибоначчи. Дерево Фибоначчи - это не сбалансированное дерево? Я думаю, что ответчика можно спутать с определением сбалансированного дерева в дереве AVL, в котором, на мой взгляд, разрешить определенное неуравновешенное дерево.
Лучшим случаем для BST является log (n), а наихудший случай - n. идея сбалансированного BST похожа на то, что вы говорите, глубина двух поддеревьев каждого узла отличается на 1 или меньше. Однако дерево AVL или дерево Red-Black являются реализацией самобалансирующегося BST, в зависимости от алгоритма они не будут реализовывать идеально сбалансированное дерево log (n), а скорее в порядке nlog (n), который намного лучше чем n. – john
Вы уверены, что его nlogn (n)? это должно быть забито (n) правильно? потому что n на самом деле лучше nlog (n) – bysreg
Ах да, это должно было быть clog (n) с c
john