Расчет высоты дерева AVL при вставке узла - PullRequest
Новая
       84

Расчет высоты дерева AVL при вставке узла

0 голосов
/ 11 апреля 2020

Я проверил в трех источниках код вставки avl. Во всех случаях для расчета высоты,

root .height = 1 + max (self.getHeight (root .left), self.getHeight (root .right))

приведена строка выше.

Вот мой запрос, почему мы должны взять максимум левого и правого поддерева и добавить к нему одно? Что если мы добавим узел к поддереву с минимальной высотой? В этом случае оба будут иметь одинаковую высоту H , а не H + 1 .

Этот прирост высоты должен быть добавлен как 

 elif key < root.key:    
      root.left = self.insertNode(root.left, key)  
      root.height = 1 + self.getHeight(root.left)
 else:    
      root.right = self.insertNode(root.right, key)
      root.height = 1 + self.getHeight(root.right )

Я прав? Если да, то почему эти люди добавляют один после приема макс?

Пожалуйста, используйте полный код для проверки ниже. Код взят с сайта programiz.com. Также проверенный компьютерщик для гиков. 

def insertNode(self, root, key): 

        if not root: 
            return TreeNode(key) 
        elif key < root.key: 
            root.left = self.insertNode(root.left, key) 
        else: 
            root.right = self.insertNode(root.right, key) 

        root.height = 1 + max(self.getHeight(root.left), 
                        self.getHeight(root.right)) 

        balanceFactor = self.getBalance(root) 

        if balanceFactor > 1:
            if key < root.left.key: 
                return self.rightRotate(root) 
            else:
                root.left = self.leftRotate(root.left) 
                return self.rightRotate(root)

        if balanceFactor < -1:
            if key > root.right.key: 
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right) 
                return self.leftRotate(root)

        return root

1 Ответ

1 голос
/ 13 апреля 2020

Предположим, у вас есть такое дерево: 

       5
      / \
     /   \
    3     7
   /     / \
  2     6   8
             \
              9

Высота дерева 3 (между 3 root узлом 5 и самым глубоким листовым узлом 9 есть 3 ветви).

Высоты поддеревьев: 1 для левого (с корнем в узле 3) и 2 для правого (с 7), и 

3 = H(node(5)) = 1 + max(H(node(3)), H(node(7))) = 1 + max(1, 2)

Теперь предположим, что вы добавили узел с ключ 4 к дереву: 

       5
      / \
     /   \
    3     7
   / \   / \
  2   4 6   8
             \
              9

Высота дерева, укорененного в узле 3, не увеличилась: H (узел (3)) по-прежнему равен 1.

Если вы предложите При замене алгоритма ваше дерево будет ошибочно получать высоту 2 после описанной вставки: 1 + H(node(3)) вместо того, чтобы поддерживать высоту равной 3.

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

...