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

  1. k-Tree
    1. Все вершины имеют от k+1 до 2k+1 детей и, соответственно, от k до 2k ключей. Корень может иметь меньше детей. Ключи и дети чередуются.
    2. Научимся делать вставку (удалении по аналогии).
    3. Определение RB-Tree. Покажем, что RB-Tree = 2-3-4-Tree
    4. 2-3-4 − излишество, достаточно потребовать 2-3. Поэтому в красно-черном достаточно разрешить красным быть только левому сыну (получили AA-дерево). Все случаи в реализации RB-дерева получаются из быстрой реализации 2-3-дерева.
  2. Крутые деревья
    1. Через Splay и Merge можно выразить Add и Delete
    2. RBST (Randonized-BST): корень − случайная вершина
    3. Декартово дерево: куча по y, BST по x. Почти RBST, но рандом генерируется не походу, а хранится в y.
  3. Забавные деревья
    1. Если размер дерева стал ровно 2k-1, перебаллансируем его полностью
    2. Если size внука в больше size-а сына, повернем
  4. Кодим
    1. Динамическое дерево отрезков [code]
    2. Не balanced дерево поиска (вставка, поиск) [code]
    3. Persistent tree (применимо к любому дерево) [code]
    4. Малое вращение. Код малого вращения. Persistent малое вращение. [code]