Как сгенерировать дерево AVL как можно более односторонним? - PullRequest
Новая
       8

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

5 голосов
/ 25 января 2012

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

1 Ответ

9 голосов
/ 25 января 2012

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

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

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

enter image description here

Деревья Фибоначчи представляют максимальную величину перекоса, которую может иметь дерево AVL, поскольку, если бы коэффициент баланса был более односторонним, коэффициент баланса каждого узла превысил бы пределы, установленные деревьями 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."

Надеюсь, это поможет!

...