Рубрики

Структуры данных | Сбалансированные деревья бинарного поиска | Вопрос 5

Рассмотрим следующее дерево AVL.

         60
      /     \  
    20      100
           /   \
         80    120     

Что из следующего является обновленным деревом AVL после вставки 70

A
        70
      /    \  
    60      100
   /       /    \
 20       80    120 

B
        100
      /    \  
    60      120
   /  \     /  
 20   70   80   


C
        80
      /    \  
    60      100
   /  \       \
 20   70      120

D
        80
      /    \  
    60      100
   /       /   \
 20      70    120  

(А) А
(Б) Б
(С) С
(D) D

Ответ: (с)
Пояснение: См. Следующие шаги для вставки AVL.

AVL Tree | Набор 1 (вставка)

After insertion of 70, tree becomes following
         60
      /     \  
    20      100
           /   \
         80    120     
        /
       70

Мы начинаем с 50 и едем вверх. Мы продолжаем путешествовать, пока не найдем неуравновешенный узел. В вышеприведенном случае мы достигаем узла 60 и видим, что 60 стал несбалансированным после вставки, и это правый левый случай . Итак, нам нужно применить два поворота

         60                               60                            80
      /     \       Right Rotate(100)  /      \     Left Rotate(60)   /    \
    20      100    -----------------> 20        80 ---------------> 60      100 
           /   \                              /   \                /  \        \
         80    120                          70     100            20   70       120  
        /                                            \    
      70                                             120 

Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Сбалансированные деревья бинарного поиска | Вопрос 5

0.00 (0%) 0 votes