АиСД-1. ПЗ-Тест №10. Бинарные деревья. Эпилог

Итак?

• AVL-дерево

• Красно-черное дерево

• Декартово дерево

• Простое случайное дерево

• Splay-дерево

Для заданной последовательности ключей и ассоциированных с ними случайных
приоритетов можно создать сколь угодно много декартовых деревьев

• А то!

• Ну, не!

Представленное неявное декартово дерево является корректным представлением массива [50, 100, 400, 300, 280].

• Однозначно!

• Не, совсем не то!

Высота декартова дерева -

• ожидаемая
  O(n)

• гарантированная O(n)

• амортизированная O(n)

• ожидаемая
  O(log n)

• амортизированная O(log n)

Листья в В-дереве...

• могут находиться на разных уровнях

• обязаны располагаться на одном и том же уровне

• не существуют

Сколько листьев будет иметь В-дерево, каждая вершина которого может иметь максимум 4 потомка, после вставки в него последовательности значений [1, 2, 3, 4, 5, 6, 7, 8]

• 1

• 2

• 3

• 4

• 5