Сбаллансированные деревья поиска (13 марта 2014)

  1. Применения Splay дерева бее доказательства
    1. Бор
      1. Можно использовать массив, список, set, hash_table
      2. Если использовать Splay дерево, то время доступа к строке длины L будет L + log|Σ|
    2. Link-Cut tree
      1. Expose = подняться до корня и объединить все куски в путь, также отрезать то, что ниже
      2. MakeRoot = Expose + Reverse
      3. Get(a, b) = MakeRoot(a) + Expose(b) + GetRoot(v[a])→value
      4. Connected(a, b) = MakeRoot(a) + Expose(b) + [Expose(v[a]) =? Expose(v[b])]
      5. Link(a, b) = MakeRoot(a) + [GetRoot(v[a])→parent := b]
      6. Потенциал = количество тяжелых ребер, которые не лежат на путях
  2. Persistent
    1. Любую структуру данных можно сделать Persistent
    2. Любое дерево делается Persistent без overhead
    3. Любой массив = дерево отрезков ⇒ Persistent с overhead в logn раз
    4. Персистент структуры требуют в logn раз больше памяти
    5. Кодим: персистентный массив и персистентный СНМ (DSU)
    6. Персистентность в Offline (обход всех версий dfs-ом, кодим на примере персистентного массива) [code]
    7. Задача про количество точек в прямоугольниках: заметающая прямая [code]
  3. Кодим
    1. struct Tree, Фиктивная нулевая вершина, вывод дерева на экран (иначе как дебажить?) [code]
    2. Дерево поиска: вставка, поиск [code]
    3. Персистентная версия [code]
    4. Идея неявного ключа (меняем две строчки) [code]
    5. Дерево отрезков для того, чтобы хранить в нем массив [code]
  4. Вращения, отцы
    1. Малое вращение.
    2. Большое вращение из AVL (zig-zag), выражение через малые вращения
    3. Большое вращение из Splay (zig-zig), выражение через малые вращения