Лучший способ вычислить высоту в дереве двоичного поиска? (балансировка AVL-дерева)

• Высота легко реализована рекурсией, возьмите максимум высоты поддеревьев плюс одно.

• "фактор баланса R" относится к правильному поддереву дерева, которое является вне баланса, я предполагаю.

Ну, можно вычислить высоту дерева со следующей рекурсивной функцией:

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

с соответствующим определением max() и struct tree. Необходимо не торопиться для выяснения, почему это соответствует определению на основе длины пути, которую Вы заключаете в кавычки. Эта функция использует нуль в качестве высоты пустого дерева.

Однако для чего-то как дерево AVL, я не думаю, что Вы на самом деле вычисляете высоту каждый раз, когда Вам нужна она. Вместо этого каждый древовидный узел увеличивается с дополнительным полем, которое помнит, что высота поддерева базировалась в том узле. Это поле должно быть усовершенствовано, поскольку дерево изменяется вставками и удалениями.

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

Вот то, где это становится сбивающим с толку, текстовые состояния, "Если фактор баланса R равняется 1, это означает, что вставка произошла на (внешней) правой стороне того узла, и левое вращение необходимо". Но от m понимание сказанного текста (поскольку я заключил в кавычки), что, если фактор баланса был в [-1, 1] затем, не было никакой потребности в балансировке?

R правый ребенок текущего узла N.

, Если balance(N) = +2, то Вам нужно какое-то вращение. Но который вращение использовать? Ну, это зависит от balance(R): если balance(R) = +1 затем Вам нужно лево-вращение на N; но если balance(R) = -1 затем Вам будет нужно какое-то двойное вращение.

Вот то, где это становится сбивающим с толку, текстовые состояния, "Если фактор баланса R равняется 1, это означает, что вставка произошла на (внешней) правой стороне того узла, и левое вращение необходимо". Но от m понимание сказанного текста (поскольку я заключил в кавычки), что, если фактор баланса был в [-1, 1] затем, не было никакой потребности в балансировке?

Хорошо, время прозрения.

Рассмотрите то, что делает вращение. Давайте думать о левом вращении.

 P = parent
 O = ourself (the element we're rotating)
 RC = right child
 LC = left child (of the right child, not of ourself)

 P
  \
   O
    \
     RC
    /
   LC

  P
   \
    RC
   /
  O
   \
    LC

 10
   \
    15
      \
       20
      /
    18

 10
   \
    20
   /
 15
   \
    18 

 basically, what happens is;

 1. our right child moves into our position
 2. we become the left child of our right child
 3. our right child's left child becomes our right

Теперь, большая вещь, которую необходимо заметить здесь - это левое вращение, НЕ ИЗМЕНИЛА ГЛУБИНУ ДЕРЕВА. Мы больше не сбалансированы для того, что сделали это.

Но - и вот волшебство в AVL - если бы мы повернули правильного ребенка направо СНАЧАЛА, что мы имели бы, это...

 P
  \
   O
    \
     LC
      \
       RC

И ТЕПЕРЬ если мы поворачиваем оставленный O, что мы получаем, это...

 P
  \
   LC
  /  \
 O    RC

Волшебство! нам удалось избавиться от уровня дерева - мы сделали древовидный баланс.

Балансировка дерева означает избавляться от избыточной глубины и упаковывать верхние уровни более полностью - который является точно, что мы только что сделали.

Тот целый материал о единственных/двойных вращениях просто, что у Вас должно быть свое поддерево, бывшее похожее на это;

 P
  \
   O
    \
     LC
      \
       RC

перед вращением - и Вам, вероятно, придется сделать, право вращается для вхождения в то состояние. Но если Вы уже находитесь в том состоянии, только необходимо сделать, левые вращаются.

Вы не должны вычислять древовидные глубины на лету.

Можно поддержать их, поскольку Вы выполняете операции.

Кроме того, Вы не должны на самом деле на самом деле поддерживать дорожку глубин; можно просто отслеживать различие между левыми и правыми древовидными глубинами.

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

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