2019-gate-computer-science-and-it-practice.pdf/Q14-alg5 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 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> | ||
| − | + | digraph G {rankdir = TB; | |
| − | 7 - | + | 7 -> 5 |
| − | 7 - | + | 7 -> 14 |
| − | 5 - | + | 5 -> 3 |
| − | 5 - | + | 5 -> 6 |
| − | 14 - | + | 14 -> 10 |
| − | 14 - | + | 14 -> 17 |
| − | 10 -- 11 | + | 10 -> h1 [style=invis] |
| + | 10 -> 11 | ||
| + | h1 [style=invis] | ||
} | } | ||
</graph> | </graph> | ||
| Строка 32: | Строка 34: | ||
14 -> 10 | 14 -> 10 | ||
14 -> 17 | 14 -> 17 | ||
| − | 10 -> 11 -> 12 | + | 10 -> h1 [style=invis] |
| + | 10 -> 11 | ||
| + | 11 -> h2 [style=invis] | ||
| + | 11 -> 12 | ||
| + | h1, h2 [style=invis] | ||
} | } | ||
</graph> | </graph> | ||
<graph> | <graph> | ||
digraph G {rankdir = TB; | digraph G {rankdir = TB; | ||
| − | 10 -> 11 -> 12 | + | 10 -> h1 [style=invis] |
| + | 10 -> 11 | ||
| + | 11 -> h2 [style=invis] | ||
| + | 11 -> 12 | ||
| + | h1, h2 [style=invis] | ||
} | } | ||
</graph> | </graph> | ||
<graph> | <graph> | ||
| − | + | digraph G {rankdir = TB; | |
11 -> 10 | 11 -> 10 | ||
11 -> 12 | 11 -> 12 | ||
| Строка 52: | Строка 62: | ||
5 -> 3 | 5 -> 3 | ||
5 -> 6 | 5 -> 6 | ||
| − | |||
14 -> 11 | 14 -> 11 | ||
11 -> 10 | 11 -> 10 | ||
11 -> 12 | 11 -> 12 | ||
| + | 14 -> 17 | ||
} | } | ||
</graph> | </graph> | ||
Текущая версия на 16:09, 25 декабря 2024
Вопрос: Q14-alg5-31d68c
Рассмотрим следующее AVL-дерево:
Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?
Ответы
- 0
- Правильный ответ: 1
- 2
- 3
Объяснение
Для балансировки достаточно сделать один левый поворот.
Исходники — вопрос 14 на 243 странице книги «2019-gate-computer-science-and-it-practice.pdf»