Операция удаления AVL в SML - PullRequest
Новая
       8

Операция удаления AVL в SML

0 голосов
/ 26 мая 2018

Я реализую дерево AVL в ML, и мне трудно реализовать операцию удаления. 

datatype 'a AVLTree = Nil | Br of ((int*('a))*('a AVLTree)*('a AVLTree));
datatype Balance = RR | LR | LL | RL;
exception NotFound;
exception NullValue;

Это то, что я получил до сих пор: 

fun remove(Nil, _)            = Nil
  | remove ((Br((i,vi), t_l, t_r)), j) = 
      case Int.compare(i,j) of 
           LESS    =>  remove(t_l,j)
         | GREATER =>  remove(t_r,j)
         | EQUAL   => (case (t_l, t_r) of
                         (Nil , _) => t_r
                        |(_,  Nil) => t_l
                        |  _       => if getHeight t_l <= getHeight t_r 
                                      then let val mk = getMinKey t_r
                                                 val mv = get(t_r,mk) 
                                           in(Br((mk,mv), t_l,(remove(t_r,mk))))
                                           end
                                      else let val mk = getMaxKey t_l
                                               val mv = get(t_l,mk)
                                  in (Br((mk,mv), (remove(t_l, mk)), t_r))end);

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

Я реализовал это такпотому что мне было трудно понять, когда использовать повороты в операции удаления.

Эта операция действительно удаляет нужный мне узел, но не сохраняет свойства дерева AVL.

Был бы рад получить помощь здесь.

1 Ответ

0 голосов
/ 28 мая 2018

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

Когда вы удаляете элемент, возможно, вам придется перебалансировать дерево.Вы не можете избежать этого, так как если бы деревья могли быть легко сбалансированы после вставки или удаления, не было бы необходимости в каком-либо дополнительном механизме для повторной балансировки.Вот несколько советов:

  • В случаях LESS и GREATER вы отбрасываете все дерево!Есть простое исправление;вы просто хотите помнить, чтобы заново построить дерево: 

    datatype 'a AVLTree = Nil | Br of (int * 'a) * 'a AVLTree * 'a AVLTree

fun remove (Nil, _) = Nil
  | remove (Br ((i, vi), tLeft, tRight), j) =
    case Int.compare (i, j) of
         LESS    => let val tRight' = remove (tRight, j)
                        val newTree = Br ((i, vi), tLeft, tRight')
                    in newTree end
       | GREATER => (* ... same, but opposite sides ... *)
       | EQUAL   => (* ... *)

  • В случаях LESS и GREATER вы забыли перебалансировать дерево после удаления элемента, если необходимо.После удаления вы можете проверить, сильно ли отличается высота, а затем выполнить соответствующее вращение.Добавление этой проверки к пути LESS может выглядеть следующим образом: 

    fun remove (Nil, _) = Nil
  | remove (Br ((i, vi), tLeft, tRight), j) =
    case Int.compare (i, j) of
         LESS    => let val tRight' = remove (tRight, j)
                        val newTree = Br ((i, vi), tLeft, tRight')
                    in if height newTree = height tRight' + 2 
                       then (* ... re-balance one way ... *)
                       else newTree
                    end
       | GREATER => (* ... same, but opposite sides; re-balance other way... *)
       | EQUAL   => (* ... *)

  • Случай EQUAL выглядит нормально.

...