AVL树LL旋转调试求助：插入21后代码异常排查

Hey there, let's dig into your AVL tree LL rotation issue—debugging these pointer-heavy rotations can be such a headache, but let's break down the likely gaps in your code step by step!

First, let's format the code snippets you shared for clarity:

Your AVL Node Class #

class avl_node {
public:
    T data;
    int value;
    int high;
    avl_node *left, *right;
    avl_node *parent;
};

Incomplete LL Rotation Code #

Status ll_rotation(avl_node<T> *v) {
    avl_node<T>* tmp = v->left;
    v->left = tmp->right;
    if (tmp->right){
        tmp->right->parent = v;
    }
    tmp->right =...

Key Issues to Fix in Your LL Rotation #

From what I can see, the most likely culprits for your post-insertion (of 21) tree structure bug are these missing pieces:

• Full Parent Pointer Updates
  You've handled the parent of tmp->right, but you're missing three critical parent pointer steps:

  1. Set tmp->parent to v's original parent
  2. Update v's original parent's left/right child pointer to point to tmp (depending on whether v was a left or right child)
  3. Set v->parent to tmp

• Height Recalculation
  AVL trees rely on accurate height tracking to maintain balance. After rotation, you must recalculate the height of both v (now tmp's right child) and tmp (the new root of this subtree). You'll want a helper function for this, like:

  int get_height(avl_node<T>* node) {
      return node ? node->high : -1; // Adjust empty node height to match your implementation
  }
  
  void update_height(avl_node<T>* node) {
      node->high = 1 + max(get_height(node->left), get_height(node->right));
  }
  

• Returning/Updating the New Root
  Your ll_rotation returns a Status, but you need to ensure the calling code gets the new root of the rotated subtree (tmp). Either pass v by reference (so you can overwrite it with tmp) or return tmp as the new root—otherwise, the rest of the tree won't know about the rotated structure.

Complete LL Rotation Example #

Here's a polished version of the rotation function that fixes these gaps:

// Helper functions first
int get_height(avl_node<T>* node) {
    return node ? node->high : -1;
}

void update_height(avl_node<T>* node) {
    node->high = 1 + max(get_height(node->left), get_height(node->right));
}

Status ll_rotation(avl_node<T>*& v) { // Use reference to update the root in place
    avl_node<T>* tmp = v->left;
    avl_node<T>* tmp_right = tmp->right;

    // Perform rotation
    tmp->right = v;
    v->left = tmp_right;

    // Update parent pointers
    if (tmp_right) {
        tmp_right->parent = v;
    }
    tmp->parent = v->parent;
    v->parent = tmp;

    // Update the grandparent's child pointer
    if (tmp->parent) {
        if (tmp->parent->left == v) {
            tmp->parent->left = tmp;
        } else {
            tmp->parent->right = tmp;
        }
    }

    // Recalculate heights (update child first, then parent)
    update_height(v);
    update_height(tmp);

    // Update the input pointer to point to the new root
    v = tmp;
    return OK; // Assume OK is your success Status value
}

Quick Note on Insertion Flow #

Don't forget: After inserting the node (21), you need to traverse up the tree from the new node, checking each ancestor's balance factor. Only trigger the LL rotation when you hit a node with a balance factor of +2 (left-heavy) whose left child is also left-heavy.

If you can share the pre-insertion tree structure and the broken post-insertion structure, we can pinpoint even more precisely, but these fixes should cover the most common LL rotation bugs.

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