伸展树（Splay Tree）实现调试求助：Rotate与Insert函数错误排查

问题描述 #

实现伸展树时出现调试问题，推测错误在Insert和Rotate函数中，但无法定位具体位置。编译运行测试用例后，旋转操作结果不符合预期，出现循环引用。

完整splay_tree类代码 #

#pragma once
#include <cassert>
#include <stdexcept>

class splay_tree {
public:
    struct node 
    {
        node(int key, node* left, node* right, node* parent) :
            key(key), left(left), right(right), parent(parent) { }

        int key;
        node* left;
        node* right;
        node* parent;
    };

    ~splay_tree() 
    {
        clear();
    }

    node* root() const 
    {
        return rt;
    }

    int size() const 
    {
        return size(rt);
    }

    bool empty() const
    {
        return rt == nullptr;
    }

    static void rotate(node* c, node* p) 
    {
        assert(c != nullptr and p != nullptr);
        assert(c == p->left or c == p->right);
        assert(c->parent == p);

        node* g = p->parent;

        if(g != nullptr) 
        {
            if (g->left == p)
                g->left = c;
            else
                g->right = c;
        } 
        else
            c->parent = nullptr;

        p->parent = c;

        if(c == p->left) 
        {
            p->left = c->right;
            if(c->right != nullptr)
                c->right->parent = p;
            c->right = p;
        }
        else{
            p->right = c->left;
            if(c->left != nullptr)
                c->left->parent = p;
            c->left = p;
        }

        if(g != nullptr)
        {
            if(p == g->left)
                g->left = c;
            else
                g->right = c;
        }
    }

    static node* splay(node* n) 
    {
        assert(n != nullptr);

        while (n->parent != nullptr) 
        {
            node* p = n->parent;
            node* g = p->parent;

            if(p == nullptr){
                rotate(n,p);
            }
            else if((p == g->left and n == p->left) or (p == g->right and n == p->right)){
                rotate(p, g);
                rotate(n, p);
            }
            else if((p == g->left and n == p->right) or (p == g->right and n == p ->left)){
                rotate(n, p);
                rotate(n, g);
            }
        }
        return n;
    }

    node* find(int k)
    {
        node* n = rt;
        node* last = nullptr;

        while(n != nullptr)
        {
            last = n;

            if(k < n->key)
                n = n->left;
            else if(k > n->key)
                n = n->right;
            else{
                return splay(n);  
            }
        }

        return splay(last);  
    }

    node* insert(int k)
    {
        if(rt == nullptr){
            rt = new node(k, nullptr, nullptr, nullptr);
            return rt;
        }

        node* n = rt;
        node* last = nullptr;

        while(n != nullptr)
        {
            if(k == n->key)
            {
                delete n; 
                return rt;
            }
            last = n;
            if(k < n->key)
                n = n->left;
            else if(k > n->key)
                n = n->right;
        }

        if(k < last->key)
        {
            last->left = new node(k, nullptr, nullptr, last);
            return splay(last->left);
        }
        else{
            last->right = new node(k, nullptr, nullptr, last);
            return splay(last->right);
        }
    }

    node* remove(int k)
    {
    
        node* n = find(k);

        if(n != nullptr and n->key == k)
        {
            node* leftSubtree = n->left;
            node* rightSubtree = n->right;

            if(leftSubtree != nullptr){
                leftSubtree->parent = nullptr;
            }

            if(rightSubtree != nullptr){
                rightSubtree->parent = nullptr;
            }

            delete n;

            if(leftSubtree == nullptr){
                return rightSubtree;
            }
            else if(rightSubtree == nullptr){
                return leftSubtree;
            }
            else{
                node* maxNode = findMax(leftSubtree);
                maxNode->right = rightSubtree;
                rightSubtree->parent = maxNode;

                return maxNode;
            }
        }   
        splay(n);
        return rt;
    }

    void set_root(node* n) 
    {
        rt = n;
    }

    void clear() 
    {
        clear(rt);
        rt = nullptr;
    }

private:
    void clear(node* n) 
    {
        if (n != nullptr) {
            clear(n->left);
            clear(n->right);
            delete n;
        }
    }

    int size(node* n) const 
    {
        if (n == nullptr) {
            return 0;
        }
        return 1 + size(n->left) + size(n->right);
    }

    node* findMax(node* n) const 
    {
        while (n->right != nullptr) {
            n = n->right;
        }
        return n;
    }

    node* rt = nullptr;
};

测试输出 #

---- Beginning tree tests ----
Testing rotation...Result of child-parent rotation (with subtrees) is incorrect:
Expected:
--- Tree structure ---
 10
 ├─(null)
 └─  2 [p = 10]
    ├─  5 [p = 2]
    │  ├─  7 [p = 5]
    │  └─  3 [p = 5]
    └─  1 [p = 2]
Actual result:
--- Tree structure ---
 10
 ├─  2 [p = 5]
 │  ├─  5 [p = 2]
 │  │  ├─  7 [p = 5]
 │  │  └─  3 [p = 5]
 │  └─  1 [p = 2]
 └─CYCLE (2)

相关资料 #

• 作业说明：Assignment Instructions
• 测试运行器：Test Runner

修复方案 #

1. 修复Rotate函数 #

问题：重复修改祖父节点g的子节点指向，且未正确设置c的parent为g，导致节点父指针混乱，出现循环引用。
修正后的Rotate函数：

static void rotate(node* c, node* p) 
{
    assert(c != nullptr and p != nullptr);
    assert(c == p->left or c == p->right);
    assert(c->parent == p);

    node* g = p->parent;

    // 设置c的父节点为g
    c->parent = g;
    // 更新g的子节点指向c（如果g存在）
    if(g != nullptr) 
    {
        if (g->left == p)
            g->left = c;
        else
            g->right = c;
    } 

    p->parent = c;

    if(c == p->left) 
    {
        p->left = c->right;
        if(c->right != nullptr)
            c->right->parent = p;
        c->right = p;
    }
    else{
        p->right = c->left;
        if(c->left != nullptr)
            c->left->parent = p;
        c->left = p;
    }
}

2. 修复Splay函数 #

问题：存在永远不会触发的if(p == nullptr)分支（循环条件是n->parent != nullptr，p不可能为空），且有一处语法空格错误。
修正后的Splay函数：

static node* splay(node* n) 
{
    assert(n != nullptr);

    while (n->parent != nullptr) 
    {
        node* p = n->parent;
        node* g = p->parent;

        if(g == nullptr){
            // 只有父节点，单旋转
            rotate(n, p);
        }
        else if((p == g->left and n == p->left) or (p == g->right and n == p->right)){
            // 一字形旋转：先转父节点，再转当前节点
            rotate(p, g);
            rotate(n, p);
        }
        else if((p == g->left and n == p->right) or (p == g->right and n == p->left)){
            // 之字形旋转：先转当前节点，再转当前节点
            rotate(n, p);
            rotate(n, g);
        }
    }
    return n;
}

3. 修复Insert函数 #

问题：当插入已存在的key时，错误删除了树中已有的节点，导致树结构损坏。
修正后的Insert函数相关片段：

while(n != nullptr)
{
    if(k == n->key)
    {
        // 已存在该key，splay后返回根节点
        return splay(n);
    }
    last = n;
    if(k < n->key)
        n = n->left;
    else if(k > n->key)
        n = n->right;
}

4. 修复Remove函数 #

问题：删除节点后未更新树的根节点rt，导致rt指向已删除的节点（悬空指针），树结构无法正确维护。
修正后的Remove函数：

node* remove(int k)
{
    node* n = find(k);

    if(n != nullptr and n->key == k)
    {
        node* leftSubtree = n->left;
        node* rightSubtree = n->right;

        if(leftSubtree != nullptr){
            leftSubtree->parent = nullptr;
        }

        if(rightSubtree != nullptr){
            rightSubtree->parent = nullptr;
        }

        delete n;

        node* newRoot = nullptr;
        if(leftSubtree == nullptr){
            newRoot = rightSubtree;
        }
        else if(rightSubtree == nullptr){
            newRoot = leftSubtree;
        }
        else{
            node* maxNode = findMax(leftSubtree);
            // 左子树最大值splay到根，保证伸展树特性
            maxNode = splay(maxNode);
            maxNode->right = rightSubtree;
            rightSubtree->parent = maxNode;
            newRoot = maxNode;
        }
        set_root(newRoot);
        return newRoot;
    }   
    // 未找到节点，splay最后访问的节点
    splay(n);
    return rt;
}

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