В1. Чем отличается идеально сбалансированное дерево от АВЛ дерева?
О1. В АВЛ-дереве для любой вершины высота ее поддеревьев различается не более, чем на 1; в идеально сбалансированном дереве такое же правило применяется для количеств вершин в поддеревьях, а не для высот.

В2. Чем отличается поиск в АВЛ-дереве от поиска в дереве двоичного поиска?
О1. Ничем, кроме того, что он эффективнее засчет равномерного распределения высот поддеревьев, то есть не может возникнуть такой ситуации, когда какое-либо поддерево представляет собой длинную лозу (односвязный список), по которой поиск будет иметь сложность O(n), где n - количество вершин в ней.

В3. Что такое хеш-таблица, каков принцип ее построения?
О3. Это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. При этом она имеет вид массива, где (в данном случае) в качестве индекса используется значение некой функции hash(k), где k - ключ, а в качестве значения -- собственно пара ключ-значение.

В4. Что такое коллизии? Каковы методы их устранения.
О4. Ситуация, когда разным ключам соответствует одно значение хеш-функции, то есть, когда hash(K1) = hash(K2), в то время как K1 ≠ K2. Среди методов разрешения коллизий можно выделить метод цепочек (к каждой ячейке таблицы привязывается связный список со всеми значениями, для которых hash() вернула индекс этой ячейки) и метод открытой адресации (если ячейка с нужным индексом уже занята, ищется следующая по порядку с шагом 1 или a*a, где a - количество уже пройденных ячеек).

В5. В каком случае поиск в хеш-таблицах становится неэффективен?
О5. Когда для поиска элемента в хэш-таблице необходимо сделать более 3-4 сравнений, разница в скорости по сравнению с АВЛ практически пропадает. В таком случае следует найти другую хэш-функцию.

В6. Эффективность поиска в АВЛ деревьях, в дереве двоичного поиска и в хеш-таблицах.
О6. См. тесты.