SML 中的 AVL 删除操作

Question

我正在 ML 中实现 AVL 树，但很难实现删除操作。

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 树的属性。

很乐意在这里获得一些帮助。

Answer 1

我的想法是找到我要删除的节点，以及它的后继节点，然后在它们之间切换并删除继任者所在的叶子，这样我就不需要平衡树了。

删除元素时，可能需要重新平衡树。您无法避免这种情况，因为如果树可以在插入或删除后毫不费力地平衡，则不需要任何额外的重新平衡机制。以下是一些提示：

• 在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的情况似乎很好。