在Standard ML中实现AVL树删除操作遇平衡维护问题求助

Hey there! I see you're working on implementing an AVL tree delete operation in Standard ML, and you've hit the tricky part of maintaining the tree's balance after removal. Your approach of replacing the target node with its predecessor or successor is totally valid—let's fix up your code to ensure it preserves the AVL properties.

First, let's recap the issue: your current remove function correctly deletes the target node, but it doesn't account for the height changes and balance violations that can happen after deletion. AVL trees require us to check and rebalance nodes as we backtrack up the recursion tree after modifying a subtree.

Step 1: Ensure you have core helper functions #

Let's start by defining (or verifying) the helper functions we'll need for height calculation, balance checks, and rotations:

Height calculation

fun getHeight Nil = 0
  | getHeight (Br(_, left, right)) = 1 + Int.max(getHeight left, getHeight right)

Balance factor calculation

This tells us how unbalanced a node is (difference between left and right subtree heights):

fun balanceFactor Nil = 0
  | balanceFactor (Br(_, left, right)) = getHeight left - getHeight right

Rotation functions

We need to handle all four AVL rotation cases (LL, RR, LR, RL):

(* LL Rotation: Right rotate to fix left-heavy left subtree *)
fun rotateLL (Br(zVal, Br(yVal, Br(xVal, a, b), c), d)) = 
    Br(yVal, Br(xVal, a, b), Br(zVal, c, d))
  | rotateLL tree = tree

(* RR Rotation: Left rotate to fix right-heavy right subtree *)
fun rotateRR (Br(xVal, a, Br(yVal, b, Br(zVal, c, d)))) = 
    Br(yVal, Br(xVal, a, b), Br(zVal, c, d))
  | rotateRR tree = tree

(* LR Rotation: Left rotate left subtree first, then right rotate root *)
fun rotateLR (Br(zVal, Br(xVal, a, Br(yVal, b, c)), d)) = 
    rotateLL (Br(zVal, rotateRR (Br(xVal, a, Br(yVal, b, c))), d))
  | rotateLR tree = tree

(* RL Rotation: Right rotate right subtree first, then left rotate root *)
fun rotateRL (Br(xVal, a, Br(zVal, Br(yVal, b, c), d))) = 
    rotateRR (Br(xVal, a, rotateLL (Br(zVal, Br(yVal, b, c), d))))
  | rotateRL tree = tree

Balance adjustment function

This checks a node's balance factor and applies the correct rotation if needed:

fun balance Nil = Nil
  | balance (Br(node, left, right)) =
    let
        val bf = balanceFactor (Br(node, left, right))
    in
        if bf > 1 then
            (* Left subtree is too heavy *)
            if balanceFactor left >= 0 then rotateLL (Br(node, left, right))
            else rotateLR (Br(node, left, right))
        else if bf < ~1 then
            (* Right subtree is too heavy *)
            if balanceFactor right <= 0 then rotateRR (Br(node, left, right))
            else rotateRL (Br(node, left, right))
        else
            (* Already balanced *)
            Br(node, left, right)
    end

Step 2: Update your remove function to maintain balance #

The key change here is that after every recursive deletion (whether in a child subtree or when removing the successor/predecessor), we rebalance the current node before returning it. Here's the revised code:

fun remove(Nil, _) = Nil
  | remove (Br((i,vi), t_l, t_r), j) =
    case Int.compare(i,j) of
        LESS => 
            (* Delete from left subtree, then rebalance current node *)
            let val newLeft = remove(t_l, j) in balance (Br((i,vi), newLeft, t_r)) end
      | GREATER => 
            (* Delete from right subtree, then rebalance current node *)
            let val newRight = remove(t_r, j) in balance (Br((i,vi), t_l, newRight)) end
      | 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)
                            (* Delete successor from right subtree, rebalance the result *)
                            val newRight = remove(t_r, mk)
                        in 
                            balance (Br((mk,mv), t_l, newRight)) 
                        end
                      else
                        let 
                            val mk = getMaxKey t_l
                            val mv = get(t_l, mk)
                            (* Delete predecessor from left subtree, rebalance the result *)
                            val newLeft = remove(t_l, mk)
                        in 
                            balance (Br((mk,mv), newLeft, t_r)) 
                        end)

Key changes explained: #

1. Recursive deletion + balance: When deleting from the left or right subtree, we first get the modified subtree, then reconstruct the current node and balance it. This ensures any balance violations from the deletion are fixed immediately.
2. Successor/predecessor cleanup: After removing the successor (or predecessor) from its subtree, we rebalance the resulting subtree before using it to construct the new root node. This prevents unbalanced subtrees from propagating up.

Verify your auxiliary functions #

Make sure your getMinKey, getMaxKey, and get functions are correctly implemented (here are standard versions for reference):

fun getMinKey (Br((i,_), Nil, _)) = i
  | getMinKey (Br(_, left, _)) = getMinKey left
  | getMinKey Nil = raise NotFound

fun getMaxKey (Br((i,_), _, Nil)) = i
  | getMaxKey (Br(_, _, right)) = getMaxKey right
  | getMaxKey Nil = raise NotFound

fun get(Nil, _) = raise NotFound
  | get(Br((i,vi), t_l, t_r), j) =
    case Int.compare(i,j) of
        LESS => get(t_l,j)
      | GREATER => get(t_r,j)
      | EQUAL => vi

Your original approach to deletion was solid—you just missed the critical step of rebalancing at every level of recursion. With these changes, your remove function will maintain the AVL tree's balance property while correctly deleting nodes.

内容的提问来源于stack exchange，提问作者genericname