基于AVL树的改进Queue结构体模板指针问题及实现疑问

问题背景 #

我正在实现一个基于AVL树的改进版Queue结构体模板，目标是支持元素向前移动操作。普通链表实现中，指定元素前移x个位置的时间复杂度为O(n)，因此选择AVL树优化。

我维护了指向最左节点的head指针（用于弹出队首）和最右节点的tail指针（用于插入队尾），还设计了jump_forward(Ref node, k)函数，可将指定节点前移k个位置靠近head。

当前存在两个问题：

• pop_first()函数因指针不一致导致段错误；
• 不确定如何维护Node的position值顺序——新插入节点的position需为当前最大值且随插入递增。

相关代码 #

template<typename T>
struct Node {
    T value;
    int position;
    Node* left;
    Node* right;
    Node* parent;
    int depth;

    Node(T val, int pos, Node* par = nullptr) : value(val), position(pos), left(nullptr), right(nullptr), parent(par), depth(1) {}
};

template<typename T>
struct Queue {
    Node<T>* root;
    Node<T>* head;
    Node<T>* tail;
    size_t count;

    Queue() : root(nullptr), head(nullptr), tail(nullptr), count(0) {}
    bool empty() const {
        return count == 0;
    }
    size_t size() const {
        return count;
    }

    struct Ref {
        Node<T>* node;
        Ref(Node<T>* n = nullptr) : node(n) {};
    };

    Ref push_last(T x) {
        // queue is empty -> create new node
        if (root == nullptr) {
            root = new Node<T>(x, count++);
            head = tail = root;
        } else {
            // attach new node as right child of current max -> rebalance
            Node<T>* newNode = new Node<T>(x, count++, tail);
            tail->right = newNode;
            tail = newNode;

            Node<T> *tmp = newNode->parent;
            // re-balancing the right subtree
            while (tmp) {
                updateDepth(tmp);
                tmp = reBalance(tmp);
                tmp = tmp->parent;
            }
        }
        return Ref(tail);

    };
    T pop_first() {
        if (empty()) throw std::out_of_range("Queue is empty");

        T headValue = head->value;
        Node<T>* oldHead = head;

        // head is root -> last element
        if(head->right == nullptr && head->parent == nullptr) {
            root = nullptr;
            head = nullptr;
            tail = nullptr;
            count = 0;
         // head is root but has right child
        } else if (head->right != nullptr && head->parent == nullptr) {
            head = head->right;
            head->parent = nullptr;
            root = head;
        // head is not root
        } else {
            // head has right child
            if (head->right) {
                head = head->right;
                head->parent = oldHead->parent;
                head->parent->left = head;
            // head has no right child
            } else {
                head = oldHead->parent;
                head->left = nullptr;
            }
        }
        delete oldHead;
        count--;

        if(root) {
            Node<T> *tmp = head->parent;
            // re-balancing the left subtree
            while (tmp) {
                updateDepth(tmp);
                tmp= reBalance(tmp);
                tmp = tmp->parent;
            }
        }
        return headValue;
    }; // throw std::out_of_range if empty

    int getDepth(Node<T> *node) const {
        return node ? node->depth : 0;
    }
    void updateParent(Node<T>* child, Node<T>* parent) {
        if (child) {
            child->parent = parent;
        }
    }
    void updateDepth(Node<T> *node) {
        if (node) {
            node->depth = std::max(getDepth(node->left), getDepth(node->right)) + 1;
        }
    }
    int getBalanceFactor(Node<T>* node) const {
        if (!node) return 0;
        return getDepth(node->left) - getDepth(node->right);
    }
    Node<T>* rightRotate(Node<T>* y) {
        Node<T>* x = y->left;
        Node<T>* T2 = x->right;

        x->right = y;
        y->left = T2;

        updateParent(T2, y);
        updateParent(x, y->parent);
        updateParent(y, x);

        if (y == root) {
            root = x;
            x->parent = nullptr;
        }
        updateDepth(y);
        updateDepth(x);

        return x;
    }

    Node<T>* leftRotate(Node<T>* x) {
        Node<T>* y = x->right;
        Node<T>* T2 = y->left;

        y->left = x;
        x->right = T2;

        updateParent(T2, x);
        updateParent(y, x->parent);
        updateParent(x, y);

        if (x == root) {
            root = y;
            y->parent = nullptr;
        }

        updateDepth(x);
        updateDepth(y);

        return y;
    }

    Node<T>* reBalance(Node<T>* node) {

        int balance = getBalanceFactor(node);

        // Right heavy
        if (balance > 1) {
            if (getBalanceFactor(node->left) < 0)
                node->left = leftRotate(node->left);
            return rightRotate(node); }

        // Left heavy
        if (balance < -1) {
            if (getBalanceFactor(node->right) > 0)
                node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        return node;
    }
};

问题1：修复pop_first()的段错误 #

核心问题 #

原代码处理head节点时，错误地将head的右子节点直接作为新head，忽略了AVL树中head的后继应该是右子树的最左节点。同时，删除节点后的平衡起始节点选择错误，导致指针悬空或树结构破坏。

修复后的pop_first()实现 #

T pop_first() {
    if (empty()) throw std::out_of_range("Queue is empty");

    Node<T>* oldHead = head;
    T headValue = oldHead->value;

    // 找到head的后继节点：右子树的最左节点，即下一个队首元素
    Node<T>* successor = oldHead->right;
    while (successor && successor->left) {
        successor = successor->left;
    }

    // 情况1：当前是最后一个节点
    if (!oldHead->parent && !oldHead->left && !oldHead->right) {
        root = nullptr;
        head = nullptr;
        tail = nullptr;
        count = 0;
    }
    // 情况2：head没有后继（无右子树）
    else if (!successor) {
        Node<T>* parent = oldHead->parent;
        if (parent) {
            parent->left = nullptr; // head是父节点的左孩子
            head = parent;
            // 从父节点开始向上平衡
            Node<T>* tmp = parent;
            while (tmp) {
                updateDepth(tmp);
                tmp = reBalance(tmp);
                tmp = tmp->parent;
            }
        } else {
            // 理论上此分支不会触发，因为无父节点且无后继意味着是最后一个节点，已被情况1处理
            root = nullptr;
            head = nullptr;
            tail = nullptr;
            count = 0;
        }
    }
    // 情况3：head有后继
    else {
        // 断开后继与原父节点的连接
        if (successor->parent != oldHead) {
            successor->parent->left = successor->right;
            if (successor->right) {
                successor->right->parent = successor->parent;
            }
            // 将后继的右子树设为原head的右子树
            successor->right = oldHead->right;
            if (oldHead->right) {
                oldHead->right->parent = successor;
            }
        }
        // 处理原head的父节点连接
        Node<T>* parent = oldHead->parent;
        successor->parent = parent;
        if (parent) {
            parent->left = successor;
        } else {
            root = successor; // 原head是根，后继成为新根
        }
        head = successor;
        // 从后继的父节点开始向上平衡
        Node<T>* tmp = successor->parent;
        while (tmp) {
            updateDepth(tmp);
            tmp = reBalance(tmp);
            tmp = tmp->parent;
        }
    }

    delete oldHead;
    count--;
    return headValue;
}

关键修复点 #

• 正确定位head的后继节点：右子树的最左节点，符合AVL树的顺序性质；
• 处理后继节点的父节点与子节点连接，避免指针悬空；
• 从受影响的父节点开始向上重新平衡，保证树的AVL性质；
• 覆盖所有边界场景，包括最后一个节点、无后继节点等。

问题2：维护position值的递增顺序 #

核心思路 #

position值需要保证唯一且严格递增，同时满足AVL树的二叉搜索性质（左子树position < 当前节点position < 右子树position）。旋转操作不会改变节点的position，因此只需在插入和移动时维护好position的赋值逻辑。

实现方案 #

1. 插入时的position赋值：
   不能使用count++，因为删除元素后count会递减，导致position重复。新增max_position变量独立维护当前最大position值：

   • 修改Queue结构体成员：

     size_t count;
     int max_position; // 新增，记录当前最大position
     

   • 构造函数初始化：

     Queue() : root(nullptr), head(nullptr), tail(nullptr), count(0), max_position(0) {}
     

   • 修改push_last中的position赋值：

     // 空队列时
     root = new Node<T>(x, max_position++, nullptr);
     // 非空时
     Node<T>* newNode = new Node<T>(x, max_position++, tail);
     

2. jump_forward操作的position调整：
   当需要将节点前移k个位置时，需调整其position为当前前驱节点position与原position之间的间隙值，保证唯一性：

   • 找到目标节点的前驱节点（顺序上的前一个节点，即左子树的最右节点，或父节点中第一个左孩子的祖先）；
   • 计算新position：new_pos = prev_pos + (target_pos - prev_pos) / (k+1)，确保新position比前驱大、比原position小；
   • 将目标节点从原位置删除，以新position重新插入AVL树，然后执行平衡操作。

注意事项 #

• position必须全局唯一，否则AVL树的顺序会被破坏；
• 插入时始终使用递增的max_position，保证新节点的position是当前最大值；
• 移动节点时通过间隙值调整position，避免与其他节点冲突。

内容的提问来源于stack exchange，提问作者Marek Pospíšil