Как вставить O(log(n)) в Data.Set?
Просматривая документы Data.SetЯ видел, что вставка элемента в дерево упоминается как O(log (n)). Тем не менее, я бы интуитивно ожидал, что он будет O(n * log (n)) (или, может быть, O(n)?), Поскольку прозрачность ссылок требует создания полной копии предыдущего дерева в O(n).
Я понимаю что например (:) можно сделать O(1) вместо O(n), так как здесь полный список копировать не нужно; новый список может быть оптимизирован компилятором как первый элемент плюс указатель на старый список (обратите внимание, что это компилятор, а не языковой уровень - оптимизация). Тем не менее, вставка значения в Data.Set включает в себя перебалансировку, которая выглядит довольно сложной для меня, и я сомневаюсь, что есть что-то похожее на оптимизацию списка Я попытался прочитать статью, на которую ссылаются Set Docs, но не смог ответить на мой вопрос.
Итак: как можно вставить элемент в двоичное дерево как O(log (n)) на (чисто) функциональном языке?
2 ответа
Нет необходимости делать полную копию Set для того, чтобы вставить элемент в него. Внутренне, элементы хранятся в дереве, что означает, что вам нужно только создавать новые узлы вдоль пути вставки. Нетронутые узлы могут быть разделены между версией до и после вставки Set, И, как указал Дейтрих Эпп, в сбалансированном дереве O(log(n)) это длина пути вставки. (Извините, что пропустил этот важный факт.)
Скажи свой Tree Тип выглядит так:
data Tree a = Node a (Tree a) (Tree a)
| Leaf
... и сказать, что у вас есть Tree это выглядит так
let t = Node 10 tl (Node 15 Leaf tr')
... где tl а также tr' некоторые именованные поддеревья. Теперь скажите, что вы хотите вставить 12 в это дерево. Ну, это будет выглядеть примерно так:
let t' = Node 10 tl (Node 15 (Node 12 Leaf Leaf) tr')
Поддеревья tl а также tr' делятся между t а также t', и вам нужно было только построить 3 новых Nodes сделать это, хотя размер t может быть намного больше, чем 3.
РЕДАКТИРОВАТЬ: Ребалансировка
Что касается перебалансировки, подумайте об этом так, и отметьте, что я не претендую на строгость здесь. Скажем, у вас есть пустое дерево. Уже сбалансировано! Теперь скажите, что вы вставили элемент. Уже сбалансировано! Теперь скажите, что вы вставили еще один элемент. Ну, есть нечетное число, поэтому вы не можете сделать там много.
Вот сложная часть. Скажем, вы вставили еще один элемент. Это может пойти двумя путями: влево или вправо; сбалансированный или несбалансированный. В случае, если он не сбалансирован, вы можете четко выполнить поворот дерева, чтобы сбалансировать его. В том случае, если он сбалансирован, уже сбалансирован!
Здесь важно отметить, что вы постоянно восстанавливаете равновесие. Это не значит, что у вас есть беспорядок в дереве, вы решили вставить элемент, но прежде чем вы это сделаете, вы делаете баланс, а затем оставляете беспорядок после того, как вы завершили вставку.
Теперь скажите, что вы продолжаете вставлять элементы. Дерево станет неуравновешенным, но ненамного. И когда это происходит, во-первых, вы исправляете это немедленно, а во-вторых, исправление происходит по пути вставки, который O(log(n)) в сбалансированном дереве. Вращения в бумаге, с которой вы связаны, касаются не более трех узлов дерева, чтобы выполнить вращение. так ты делаешь O(3 * log(n)) работать при ребалансировке. Это еще O(log(n)),
Чтобы добавить дополнительный акцент на то, что сказал dave4420 в комментарии, в создании (:) работать в постоянном времени. Вы можете реализовать свой собственный тип данных списка и запустить его в простом неоптимизирующем интерпретаторе Haskell, и он все равно будет O(1).
Список определяется как начальный элемент плюс список (или он пустой в базовом случае). Вот определение, которое эквивалентно родным спискам:
data List a = Nil | Cons a (List a)
Так что если у вас есть элемент и список, и вы хотите построить из них новый список с помощью Consэто просто создание новой структуры данных непосредственно из аргументов, требуемых конструктором. Больше нет необходимости даже проверять хвостовой список (не говоря уже о его копировании), чем проверять или копировать строку, когда вы делаете что-то вроде Person "Fred",
Вы просто ошибаетесь, когда утверждаете, что это оптимизация компилятора, а не языковой уровень. Это поведение следует непосредственно из определения уровня языка типа данных списка.
Точно так же для дерева, определенного как элемент плюс два дерева (или пустое дерево), когда вы вставляете элемент в непустое дерево, он должен входить в левое или правое поддерево. Вам нужно будет создать новую версию этого дерева, содержащего элемент, что означает, что вам нужно будет создать новый родительский узел, содержащий новое поддерево. Но другое поддерево совсем не нужно пересматривать; это может быть помещено в новое родительское дерево как есть. В сбалансированном дереве это полная половина дерева, которой можно поделиться.
Применение этих рассуждений рекурсивно должно показать вам, что на самом деле копирование элементов данных вообще не требуется; есть только новые родительские узлы, необходимые на пути к конечной позиции вставленного элемента. Каждый новый узел хранит 3 вещи: элемент (совместно используемый со ссылкой на элемент в исходном дереве), неизменное поддерево (совместно используемое с исходным деревом) и вновь созданное поддерево (которое разделяет почти всю свою структуру с исходной дерево). Там будет O(log(n)) из них в сбалансированном дереве.