Как генерировать дерево AVL как можно более однобоко?

Question

Я видел это в какой-то статье, и кто-то утверждал, что при удалении узла дерева AVL может быть не более часа (n) раз вращение. Я считаю, что мы можем добиться этого, создав дерево AVL как можно более изогнутым. Проблема в том, как это сделать. Это поможет мне много узнать об исследовании операции удаления. Огромное спасибо!

Answer 1

Если вы хотите, чтобы сделать максимально криво AVL дерева, вы ищете Fibonacci tree, которая определяется индуктивно следующим образом:

• Фибоначчи дерево порядка 0 пусто.
• Дерево Фибоначчи порядка 1 - это единственный узел.
• Фибоначчи дерево порядка п + 2 является узлом, левая ребенок Фибоначчи дерево порядка п и чье право ребенка является Фибоначчи дерево порядка п + 1.

Например, вот Фибоначчи дерево порядка 5:

Фибоначчи деревья представляют собой максимальную величину перекоса, что дерево АВЛ может иметь, так как если баланс фактор был больше однобокой фактор баланса каждого узла будет превышать пределов размещены по деревьям AVL.

Вы можете использовать это определение очень легко создавать максимально однобокий дерева AVL:

function FibonacciTree(int order) { 
    if order = 0, return the empty tree. 
    if order = 1, create a single node and return it. 
    otherwise: 
     let left = FibonacciTree(order - 2) 
     let right = FibonacciTree(order - 1) 
     return a tree whose left child is "left" and whose right child is "right." 

Надеется, что это помогает!