Блог

Главная - Вопросы по программированию - Должен ли я сбалансировать свои деревья AVL сверху вниз или снизу вверх?

Должен ли я сбалансировать свои деревья AVL сверху вниз или снизу вверх?

#python #data-structures #binary-tree

Вопрос:

не привязан ни к какому языку, но я покажу какой-нибудь код на python, который у меня был

 def insert(self,i):
    temp = self
    while(True):
      if i > temp.V:
        if temp.R == None:
          temp.R = node(None,None,i)
          temp = temp.R
          break
        else:
          temp = temp.R

      else:
        if temp.L == None:
          temp.L = node(None,None,i)
          temp = temp.L
          break
        else:
          temp = temp.L

    self = self.balance()

и для узла класса

 def __init__(self,left,right,val):
    self.L = left
    self.R = right
    self.V = val

при методе сверху вниз и вставка, и балансировка являются отдельными функциями, что, я думаю, было бы хорошо с точки зрения абстракции?? Это также позволяет мне выполнять вставку итеративно [и итерация быстрее, чем рекурсия-это то, чему меня учили]

между тем метод снизу вверх выполняет балансировку в [предположительно меньшем количестве] операций, но также должен быть связан со вставкой для работы. Это также означает, что я должен вставлять элементы рекурсивно, что дороже, чем итерация.

Пожалуйста, поправьте меня, если мои рассуждения неверны, потому что мне оба кажутся достойными подходами.

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

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

Комментарии:

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

Ответ №1:

Недостатком подхода «сверху вниз» является то, что вы не можете полагаться на информацию о балансе, хранящуюся в узле AVL (-1, 0 или 1), поскольку она не отражает эффект последней вставки-только вставленный узел получил обновленную информацию о балансе, которая еще не была выведена (пока). Таким образом, это означает, что вызов balance функции (которая не принимает никаких аргументов) должен будет сканировать все дерево! Таким образом, это будет представлять O(n) временную сложность.

Подход снизу вверх должен будет только просмотреть (некоторые) предки вставленного узла, которые при необходимости обновят информацию о своем балансе, возможно, после применения поворота. Это будет иметь временную сложность O(logn).

Метки: