Splay Tree搜索功能实现中Zag-zag旋转错误问题排查求助

我正在使用右斜树测试Zag-zag旋转，此前我用左斜树测试Zig-zig、Zig-zag旋转均运行正常。

问题代码 #

// 伸展树节点定义
class Node {
  constructor(key) {
    this.key = key;
    this.left = this.right = null;
  }
}

function rightRotate(root) {
  const rootLeft = root.left;
  root.left = rootLeft.right;
  rootLeft.right = root;
  return rootLeft;
}

function leftRotate(root) {
  const rootRight = root.right;
  root.right = rootRight.left;
  rootRight.left = root;
  return rootRight;
}

// 原问题splay函数
function splay(root, key) {
  if (root === null || root.key === key) return root;

  if (key < root.key) {
    if (root.left === null) return root;

    // Zig-Zig (左左)
    if (key < root.left.key) {
      root.left.left = splay(root.left.left, key);
      root = rightRotate(root);
    }
    // Zig-Zag (左右)
    else if (key > root.left.key) {
      root.left.right = splay(root.left.right, key);
      if (root.left.right != null) root.left = leftRotate(root.left);
    }

    return rightRotate(root);
  }
  else {
    if (root.right === null) return root;

    // Zag-Zag (右右)
    if (key > root.right.key) {
      root.right.right = splay(root.right.right, key);
      root = leftRotate(root);
    }
    // Zag-Zig (右左)
    else if (key < root.right.key) {
      root.right.left = splay(root.right.left, key);
      if (root.right.left != null) root.right = rightRotate(root.right);
    }

    return leftRotate(root);
  }
}

function search(root, key) {
  return splay(root, key);
}

function preOrder(root) {
  if (root != null) {
    console.log(root.key);
    preOrder(root.left);
    preOrder(root.right);
  }
}

// 测试用右斜树
let root2 = new Node(10);
root2.right = new Node(15);
root2.right.right = new Node(16);
root2.right.right.right = new Node(20);
root2.right.right.right.right = new Node(21);
root2.right.right.right.right.right = new Node(22);
root2 = splay(root2, 20);
console.log(root2)

预期旋转流程 #

• Zag-zag旋转：将节点15替换为20
• Zag旋转：将节点10替换为20

故障原因 #

你的splay函数递归逻辑错误：在处理Zig-Zig、Zag-Zag场景时，你直接递归伸展孙子节点（root.left.left/root.right.right），跳过了父节点的伸展步骤，导致层级旋转次数错误，最终结构不符合预期。

正确的递归伸展逻辑应该是先递归伸展父节点，将目标节点提升到父节点位置后，再执行两次对应旋转完成祖孙层级的调整。

修复方案 #

仅需要修改splay函数中Zig-Zig、Zag-Zag分支的递归目标即可：

function splay(root, key) {
  if (root === null || root.key === key) return root;

  if (key < root.key) {
    if (root.left === null) return root;

    // Zig-Zig (左左)
    if (key < root.left.key) {
      // 先递归伸展父节点，将key提升到root.left位置
      root.left = splay(root.left, key);
      root = rightRotate(root);
    }
    // Zig-Zag (左右)
    else if (key > root.left.key) {
      root.left.right = splay(root.left.right, key);
      if (root.left.right != null) root.left = leftRotate(root.left);
    }

    return rightRotate(root);
  }
  else {
    if (root.right === null) return root;

    // Zag-Zag (右右)
    if (key > root.right.key) {
      // 先递归伸展父节点，将key提升到root.right位置
      root.right = splay(root.right, key);
      root = leftRotate(root);
    }
    // Zag-Zig (右左)
    else if (key < root.right.key) {
      root.right.left = splay(root.right.left, key);
      if (root.right.left != null) root.right = rightRotate(root.right);
    }

    return leftRotate(root);
  }
}

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