设计支持访问后移至头部的高效索引访问数据结构

首先，咱们明确核心需求：能像数组那样按索引快速访问元素，而且访问第i个元素后必须把它移到结构的头部，同时要比链表的O(n)访问复杂度更优，还禁止插入操作。

最优选择：带子树大小的Splay Tree #

Splay Tree（伸展树）简直是为这个需求量身定做的——它的核心特性就是每次访问节点后，会自动将该节点旋转到树的根位置（完美对应"移至头部"的要求）。同时，只要给每个节点维护一个size属性（记录当前节点子树的总节点数），就能在O(log n)时间内找到第k个元素。

下面是一个简化的Python实现，刚好匹配你的示例场景：

class SplayNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.size = 1  # 子树节点总数（包括自身）

    def update_size(self):
        # 更新当前节点的size
        self.size = 1
        if self.left:
            self.size += self.left.size
        if self.right:
            self.size += self.right.size

class SplayTree:
    def __init__(self, values):
        self.root = self.build_tree(values, 0, len(values)-1)

    def build_tree(self, values, l, r):
        # 递归构建平衡的初始树
        if l > r:
            return None
        mid = (l + r) // 2
        node = SplayNode(values[mid])
        node.left = self.build_tree(values, l, mid-1)
        node.right = self.build_tree(values, mid+1, r)
        node.update_size()
        return node

    def _rotate_left(self, x):
        # 左旋操作
        y = x.right
        x.right = y.left
        y.left = x
        x.update_size()
        y.update_size()
        return y

    def _rotate_right(self, x):
        # 右旋操作
        y = x.left
        x.left = y.right
        y.right = x
        x.update_size()
        y.update_size()
        return y

    def _splay(self, node, k):
        # 将第k个节点splay到当前子树的根
        left_size = node.left.size if node.left else 0
        if k == left_size:
            # 找到目标节点
            return node
        elif k < left_size:
            # 目标在左子树
            if not node.left:
                return node
            left_left_size = node.left.left.size if node.left.left else 0
            if k < left_left_size:
                # 右旋两次（zig-zig）
                node.left.left = self._splay(node.left.left, k)
                node = self._rotate_right(node)
            elif k > left_left_size:
                # 先左旋再右旋（zig-zag）
                node.left.right = self._splay(node.left.right, k - left_left_size - 1)
                if node.left.right:
                    node.left = self._rotate_left(node.left)
            if node.left:
                node = self._rotate_right(node)
            return node
        else:
            # 目标在右子树
            if not node.right:
                return node
            k -= left_size + 1
            right_left_size = node.right.left.size if node.right.left else 0
            if k < right_left_size:
                # 先右旋再左旋（zag-zig）
                node.right.left = self._splay(node.right.left, k)
                if node.right.left:
                    node.right = self._rotate_right(node.right)
            elif k > right_left_size:
                # 左旋两次（zag-zag）
                node.right.right = self._splay(node.right.right, k - right_left_size - 1)
                node = self._rotate_left(node)
            if node.right:
                node = self._rotate_left(node)
            return node

    def access(self, index):
        # 访问第index个元素，然后移到头部（根）
        if index < 0 or index >= self.root.size:
            raise IndexError("Index out of range")
        self.root = self._splay(self.root, index)
        return self.root.value

    def to_list(self):
        # 将树转换为数组形式，方便查看状态
        result = []
        def inorder(node):
            if node:
                inorder(node.left)
                result.append(node.value)
                inorder(node.right)
        inorder(self.root)
        return result

# 测试你的示例场景
t = SplayTree([5,4,9,45])
print("初始状态:", t.to_list())  # [5,4,9,45]
print("访问索引2，返回:", t.access(2))  # 9
print("当前状态:", t.to_list())  # [9,5,4,45]
print("访问索引3，返回:", t.access(3))  # 45
print("当前状态:", t.to_list())  # [45,9,5,4]
print("访问索引0，返回:", t.access(0))  #45
print("当前状态:", t.to_list())  # [45,9,5,4]
print("访问索引2，返回:", t.access(2))  #5
print("当前状态:", t.to_list())  # [5,45,9,4]

关于Cartesian Tree和Ropes的适用性对比 #

咱们逐个拆解：

• Cartesian Tree：它的核心是同时满足二叉搜索树的中序遍历顺序和堆的优先级属性（比如父节点值大于子节点）。它主要用于区间最值查询（RMQ）这类静态场景，一旦构建完成，调整节点位置会严重破坏它的堆或BST属性，要把某个节点移到头部的操作复杂度极高，完全不适合咱们的动态访问后移动需求。
• Ropes：这是专门为大字符串设计的结构，本质是存储子串长度的平衡二叉树，优化点在高效的字符串分割、拼接和切片操作。虽然理论上可以改造实现"访问后移到头部"，但这不是它的设计目标，操作效率远不如Splay Tree，属于用错了工具。

所以结论很明确：Splay Tree是最适合这个需求的结构，而Cartesian Tree和Ropes都不适用。

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