基于访问计数优化的BST节点上移旋转次数不符合预期问题排查

问题根因 #

你的代码存在3个核心错误，导致高访问计数节点最多只能上浮1层：

• 子节点缓存错误：你在进入当前节点处理逻辑时就提前缓存了left、right为原currentNode的左右子节点，当执行完一次旋转后，currentNode已经更新为新的节点，此时你判断的还是旧的子节点访问计数，无法触发二次旋转。
• 后序遍历逻辑缺陷：你采用先递归处理子节点、再处理当前节点的后序遍历顺序，当你把高访问计数的子节点旋转为当前节点的父节点后，已经完成了子节点的处理流程，不会再回溯向上调整更上层的节点，直接终止了上浮过程。
• 无效全树遍历风险：每次优化都从根节点做全树遍历，不仅性能差，还可能触发其他未访问节点的意外旋转，不符合访问计数优化BST的设计逻辑。

修复方案 #

推荐方案：改为沿访问路径向上逐层调整 #

放弃全树后序遍历的实现，在find方法定位到目标节点后，沿着目标节点到根的路径逐层向上判断旋转，直到节点访问计数不大于父节点或到达根节点。
首先需要给TreeNode类新增parent字段，用于记录节点的父节点引用，替换原有RecOptimize的代码如下：

private void OptimizeAccessNode(TreeNode<T> target)
{
    TreeNode<T> cur = target;
    TreeNode<T> parent = cur.parent;

    while (parent != null && cur.iAccessCount > parent.iAccessCount)
    {
        TreeNode<T> grandParent = parent.parent;
        // 判断当前节点是父节点的左/右子节点，执行对应旋转
        if (parent.left == cur)
        {
            parent = MakeLeftRoot(parent);
        }
        else
        {
            parent = MakeRightRoot(parent);
        }
        // 更新祖父节点的指向
        if (grandParent != null)
        {
            if (grandParent.left == parent.left)
            {
                grandParent.left = parent;
            }
            else
            {
                grandParent.right = parent;
            }
        }
        else
        {
            this.rootNode = parent;
        }
        // 更新父节点指针
        parent.parent = grandParent;
        cur.parent = parent;
        if (parent.left != null) parent.left.parent = parent;
        if (parent.right != null) parent.right.parent = parent;
        // 继续向上层判断
        cur = parent;
        parent = cur.parent;
    }
}

兼容原有逻辑的修复方案 #

如果不想调整整体遍历逻辑，只需修改原有RecOptimize的两个问题点即可：

1. 移除提前缓存左右子节点的逻辑，每次判断都取当前节点的最新子节点
2. 增加循环判断，直到当前节点的左右子节点访问计数都不大于当前节点，再向上返回
   修改后的代码如下：

private void RecOptimize(TreeNode<T> currentNode, TreeNode<T> prevNode)
{
    if (currentNode == null) return;

    RecOptimize(currentNode.left, currentNode);
    RecOptimize(currentNode.right, currentNode);

    var oldNode = currentNode;
    bool hasRotated;
    do
    {
        hasRotated = false;
        // 每次判断都取最新的右子节点
        if(currentNode.right != null && currentNode.right.iAccessCount > currentNode.iAccessCount)
        {
            currentNode = MakeRightRoot(currentNode);
            hasRotated = true;
        }
        // 每次判断都取最新的左子节点
        if(currentNode.left != null && currentNode.left.iAccessCount > currentNode.iAccessCount)
        {
            currentNode = MakeLeftRoot(currentNode);
            hasRotated = true;
        }
    } while (hasRotated);

    if(prevNode != null)
    {
        if(prevNode.left != null && prevNode.left.Equals(oldNode))
        {
            prevNode.left = currentNode;
        }
        if(prevNode.right != null && prevNode.right.Equals(oldNode))
        {
            prevNode.right = currentNode;
        }
    }
    else
    {
        this.rootNode = currentNode;
    }
}

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