Балансировка дерева AVL haskell

Question

Я создаю дерево AVL в Haskell, но я не уверен, как сбалансировать дерево. Я могу добавлять элементы, но они не сбалансированы. например, используя метод addList, который я добавляю в [4,2,1,3,6,8], добавляет его как:

Схема расположения: Root 4 (Root 2 (Root 1 Empty Empty) (Root 2 Empty Empty))) (Root 6 Empty (Root 8 Empty Empty))

должны быть напечатаны как:

  4 
    2  6 
1  3  8 

Я хочу, чтобы сбалансировать дерево право, но не знаю, как правильно реализовать, вот мой код до сих пор. Любая помощь в этом была бы потрясающей.

data AVLTree a = Empty | Root a (AVLTree a) (AVLTree a) 
    deriving (Eq, Ord, Show) 
leaf a = Root a Empty Empty 

addNode :: Integral a => a -> AVLTree a -> AVLTree a 
addNode a Empty = leaf a 
addNode x (Root a left right) 
    | x > a = Root a left (addNode x right) 
    | x < a = Root a (addNode x left) right 
    | otherwise = (Root a left right) 
addList :: (Integral a) => [a] -> AVLTree a 
addList [] = Empty 
addList [n] = leaf n 
addList (x:xs) = addNode x (addList xs) 



search :: Integral a => AVLTree a -> a -> Bool 
search Empty _ = False 
search (Root a left right) x 
    | x == a = True 
    | x < a = search left x 
    | x > a = search right x 

-- balance :: AVLTree a -> AVLTree a 
-- balance Empty = Empty 
-- balance tree 
-- |(Root r (Root left (Root left1 Empty Empty) Empty) Empty) = (Root left left1 r) -- left left case 
-- |(Root r Empty (Root right Empty Empty) (Root right Empty Empty)) = (Root right r right1) -- right right case 
-- |(Root r (Root left Empty (Root right Empty Empty)) Empty) = (Root r (Root right (Root left Empty Empty) Empty) Empty) -- left right case 
-- |(Root r Empty (Root right (Root left Empty Empty) Empty)) = (Root r Empty (Root left Empty (Root right Empty Empty))) -- right left case 

Answer 1

Реализация отсутствует много вещей, тем не менее, вы должны идти читать немного больше на то, что нужно (даже википедия имеет хорошее описание, но и многие другие страницы будут отображаться, если вы делаете поиск.)

Самая сложная часть написания любого (самобалансирующегося) дерева находится в балансировочном коде .... Просто создание дерева в Haskell очень просто, как вы это делали выше, но сохранение журнала поиска (N) немного сложнее. В случае AVL, вам придется добавить еще код, который делает включено следующее:

1. Добавить Int к каждому узлу, который измеряет высоту в этом узле. Высота измеряется как расстояние до самого дальнего листа. AVL работает, проверяя, что разница между высотой левого и правого субномов никогда не отличается более чем 1. Важно отметить, что эта высота должна быть добавлена ​​непосредственно к узлу и не вычисляется при необходимости (так как некоторый демонстрационный код на Интернет делает), или даже простая вставка должна пройти по всему дереву и больше не быть журналом N.

2. Добавить код, чтобы подойти к дереву узлов после вставки (возможно, лучшим местом для этого было бы быть в самой вставке, поскольку вы уже прошли по дереву до точки вставки, вы можете просто поместить чек после рекурсии). Вычислите высоту (просто добавьте один к максимальному из двух высот ниже, который вы только что рассчитали при рекурсивном вызове), и проверьте коэффициент баланса (height of right - height of left). Если ситуация неуравновешена (т. Е. |balance factor| > 1), вы должны ....

3. Позвоните в функцию поворота. Вращение - операция с типом AVLTree->AVLTree. Интуитивно он подталкивает верхние значения в дереве слева (или вправо в зависимости от направления дисбаланса), тем самым восстанавливая баланс. Правый узел становится новым верхним узлом и передает его левый узел в старый верх, который затем становится новым левым узлом. Это визуально-

a       c 
/\      /\ 
b c    ->   a e 
    /\     /\ 
    d e     b d 

Обратите внимание, что вам нужно будет вращать один или два раза в дисбалансе, в зависимости от простой проверки, что вы будете делать .... Если верх (скажем, вправо), прежде чем поворачивать верхнюю часть влево, вам может понадобиться повернуть правый узел вправо, если правый узел имеет любой дисбаланс влево (даже на 1, в отличие от верхнего , который может иметь -1, 0 или 1, и не нужно вращать). Коды вращения одинаковы, поэтому вы должны использовать ту же функцию для вращения сверху и справа (хотя вы можете иметь отдельную версию для вращения до справа или слева).

Если вы запустите этот балансировочный код для каждой вставки, этого будет достаточно ....Если вы когда-либо добавляете узлы и не делаете этого, вам может потребоваться повторить этот процесс несколько раз на всех узлах до того, как дерево будет сбалансировано, и это потребует больше, чем логарифмических (N) вычислений ....

Поскольку я написал это, я заметил, что я едва написал какую-либо информацию Haskell ... Эта информация будет работать на любом языке. Я полагаю, что так и должно быть, нет причин, по которым реализация должна отличаться только потому, что мы находимся в Haskell. Если у вас возникли проблемы с отображением Haskell, как бы это было сделано, просто спросите в комментариях, и я также могу заполнить это.

Также обратите внимание, что если вы просто хотите объект с вводом/удалением Log (N), у Haskell уже есть тип Data.Sequence. Если это сработает для вас, вам не придется писать об этом сами.

---

Edited обратиться comments-

Функции высоты вы упоминаете есть проблема, я уже упоминал выше- Вы рекурсии через все дерево, чтобы найти высоту любого узла. Вложения больше не будут иметь сложность log N, которая сводит на нет всю суть создания дерева. (Насколько я знаю, Haskell не запоминает ни одно из этих значений .... Если кто-то знает иначе, не стесняйтесь звонить, это упростит этот код).

Выработать немного больше, вы хотите расширить определение AVLTree как this-

data AVLTree a = Empty | Node a (AVLTree a) (AVLTree a) Int 

Теперь высота всего полученного как this-

height (AVLTree _ _ _ height) = height 

Тогда ваш balanceFactor работы-

balanceFactor :: AVLTree a -> Int 
balanceFactor Empty = 0 
balanceFactor (Root a left right) = (height right) - (height left) 

Недостатком является то, что вам придется добавить код для пересчета высоты u p целую цепочку к корню после изменения.

Затем вам нужно будет написать еще одну функцию, которая проверяет, является ли ротация необходима, и применяет его, если needed-

rotateIfNeeded::AVLTree->AVLTree 
rotateIfNeeded tree 
    | b > 1 = fullRotateLeft tree 
    | b < -1 = fullRotateRight tree 
    | otherwise = tree 
     where b = balanceFactor tree 

Функции fullRotateLeft/fullRotateRight являются обертками вокруг rotateLeft/rotateRight, что первый чек, если справа/слева деревья сначала должны иметь обратное вращение, а затем применить все необходимые вращения.

Ваша функция rotateRight/rotateLeft не будет работать. Слишком много переменных слева заполняются пустым, так много случаев не хватает. Вы хотите заполнить большинство из них переменными и перенести их в нужное место справа.