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

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


algorithm data-structures avl-tree
person Yuming Cao    schedule 25.01.2012    source источник
comment
См. также: stackoverflow.com/ вопросы/19622572/   -  person Walter Tross    schedule 06.11.2013

Ответы (1)


arrow_upward
9
arrow_downward

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

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

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

введите здесь описание изображения

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

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

person templatetypedef    schedule 25.01.2012
comment
Хороший ответ. Лишь бы к ней был образ. - person ; 25.01.2012
comment
(Обратите внимание, в частности, что каждый нелист имеет коэффициент баланса, отличный от 0.) - person Erik P.; 25.01.2012