2019-gate-computer-science-and-it-practice.pdf/Q14-alg5 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии этого же участника)
Строка 2: Строка 2:
 
Рассмотрим следующее [https://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE AVL-дерево]:
 
Рассмотрим следующее [https://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE AVL-дерево]:
 
<graph>
 
<graph>
−
graph G {rankdir = TB;  
+
digraph G {rankdir = TB;  
−
   7 -- 5
+
   7 -> 5
−
   7 -- 14
+
   7 -> 14
−
   5 -- 3
+
   5 -> 3
−
   5 -- 6
+
   5 -> 6
−
   14 -- 10
+
   14 -> 10
−
   14 -- 17
+
   14 -> 17
−
   10 -- 11
+
   10 -> h1 [style=invis]
 +
  10 -> 11
 +
  h1 [style=invis]
 
}
 
}
 
</graph>
 
</graph>
Строка 23: Строка 25:
 
=== Объяснение ===
 
=== Объяснение ===
 
Для балансировки достаточно сделать один левый поворот.
 
Для балансировки достаточно сделать один левый поворот.
 +
 +
<graph>
 +
digraph G {rankdir = TB;
 +
  7 -> 5
 +
  7 -> 14
 +
  5 -> 3
 +
  5 -> 6
 +
  14 -> 10
 +
  14 -> 17
 +
  10 -> h1 [style=invis]
 +
  10 -> 11
 +
  11 -> h2 [style=invis]
 +
  11 -> 12
 +
  h1, h2 [style=invis]
 +
}
 +
</graph>
 +
<graph>
 +
digraph G {rankdir = TB;
 +
  10 -> h1 [style=invis]
 +
  10 -> 11
 +
  11 -> h2 [style=invis]
 +
  11 -> 12
 +
  h1, h2 [style=invis]
 +
}
 +
</graph>
 +
<graph>
 +
digraph G {rankdir = TB;
 +
  11 -> 10
 +
  11 -> 12
 +
}
 +
</graph>
 +
<graph>
 +
digraph G {rankdir = TB;
 +
  7 -> 5
 +
  7 -> 14
 +
  5 -> 3
 +
  5 -> 6
 +
  14 -> 11
 +
  11 -> 10
 +
  11 -> 12
 +
  14 -> 17
 +
}
 +
</graph>
 +
  
 
{{cstest-source|2019-gate-computer-science-and-it-practice.pdf|243|14}}
 
{{cstest-source|2019-gate-computer-science-and-it-practice.pdf|243|14}}

Текущая версия на 16:09, 25 декабря 2024

Вопрос: Q14-alg5-31d68c

Рассмотрим следующее AVL-дерево: [svg]

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

Ответы

  • 0
  • Правильный ответ: 1
  • 2
  • 3

Объяснение

Для балансировки достаточно сделать один левый поворот.

[svg] [svg] [svg] [svg]


Исходники — вопрос 14 на 243 странице книги «2019-gate-computer-science-and-it-practice.pdf»

Источник — «https://discopal.ispras.ru/index.php?title=2019-gate-computer-science-and-it-practice.pdf/Q14-alg5&oldid=35090»