Dart中SplayTreeSet如何优雅获取前后元素？

首先明确：直接用index±1的方式不可行。SplayTree是自平衡二叉搜索树，节点并非按数组式连续存储，index是逻辑遍历顺序的计数，要通过index定位节点需要从根开始遍历计数，最坏时间复杂度O(n)，效率极低，完全违背SplayTree的设计优势。

下面是基于SplayTree节点结构的优雅实现方案，核心利用二叉搜索树的前驱/后继特性，结合SplayTree的节点指针（每个节点需维护left、right、parent指针）：

1. 获取后继节点（next） #

后继节点是当前节点在中序遍历中的下一个节点，实现逻辑：

• 如果当前节点存在右子树，后继是右子树中最左侧的节点（即右子树的最小节点）
• 如果没有右子树，向上遍历父节点，直到找到一个父节点，使得当前节点是该父节点的左子节点，这个父节点就是后继
• 若遍历到根节点仍未找到，说明当前节点是树的最后一个节点，无后继

示例JS伪代码：

function getNext(node) {
  // 右子树存在，找右子树最左节点
  if (node.right) {
    let current = node.right;
    while (current.left) {
      current = current.left;
    }
    return current;
  }
  // 向上找符合条件的父节点
  let parent = node.parent;
  let current = node;
  while (parent && current === parent.right) {
    current = parent;
    parent = parent.parent;
  }
  return parent;
}

2. 获取前驱节点（previous） #

前驱节点是当前节点在中序遍历中的前一个节点，实现逻辑：

• 如果当前节点存在左子树，前驱是左子树中最右侧的节点（即左子树的最大节点）
• 如果没有左子树，向上遍历父节点，直到找到一个父节点，使得当前节点是该父节点的右子节点，这个父节点就是前驱
• 若遍历到根节点仍未找到，说明当前节点是树的第一个节点，无前驱

示例JS伪代码：

function getPrevious(node) {
  // 左子树存在，找左子树最右节点
  if (node.left) {
    let current = node.left;
    while (current.right) {
      current = current.right;
    }
    return current;
  }
  // 向上找符合条件的父节点
  let parent = node.parent;
  let current = node;
  while (parent && current === parent.left) {
    current = parent;
    parent = parent.parent;
  }
  return parent;
}

补充说明 #

这种实现的平均时间复杂度为O(log n)，因为SplayTree的自调整特性会将访问过的节点移到根附近，后续重复访问的效率会更高。只要你的SplayTree实现中每个节点维护了left、right、parent三个指针，就能直接复用上述逻辑。

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