Python游戏排行榜同分排名异常问题排查求助

需求概述 #

需实现高效支持以下三种操作的游戏排行榜：

• add_score player_id score：更新玩家分数（新分数不高于当前则忽略）
• get_rank player_id：返回玩家排名（排名1为最高分，同分玩家共享排名）
• get_score_by_rank rank：返回指定排名对应的分数（同分玩家共享排名）

示例操作与输出 #

<< in
add_score 1 100
get_rank 1
add_score 1 120
get_rank 1
add_score 2 100
get_rank 1
get_rank 2
get_score_by_rank 1

>> out
1
1
1
1
2
1
2
120

问题描述 #

采用AVL树实现后，短序列测试正常，但多次更新后出现排名计算错误：例如存在同分玩家时，后续玩家的排名未跳过同分人数（如预期同分玩家排名为118、118，下一名应为120，但实际输出121）。

代码实现 #

import sys

class AVLNode:
    def __init__(self, score):
        self.score = score
        self.players = set()
        self.count = 0
        self.height = 1
        self.left = None
        self.right = None
        self.total = 0

class AVLTree:
    def __init__(self):
        self.root = None

    def _height(self, node):
        return node.height if node else 0

    def _update(self, node):
        if not node:
            return
        node.height = 1 + max(self._height(node.left), self._height(node.right))
        left_total = node.left.total if node.left else 0
        right_total = node.right.total if node.right else 0
        node.total = left_total + right_total + node.count

    def _balance_factor(self, node):
        return self._height(node.left) - self._height(node.right)

    def _rotate_left(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        self._update(z)
        self._update(y)
        return y

    def _rotate_right(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        self._update(z)
        self._update(y)
        return y

    def _balance(self, node):
        if not node:
            return node
        balance = self._balance_factor(node)
        if balance > 1:
            if self._balance_factor(node.left) < 0:
                node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        if balance < -1:
            if self._balance_factor(node.right) > 0:
                node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
        return node

    def _insert(self, node, score, player_id):
        if not node:
            new_node = AVLNode(score)
            new_node.players.add(player_id)
            new_node.count = 1
            new_node.total = 1
            return new_node

        if score > node.score:
            node.left = self._insert(node.left, score, player_id)
        elif score < node.score:
            node.right = self._insert(node.right, score, player_id)
        else:
            if player_id not in node.players:
                node.players.add(player_id)
                node.count += 1
                node.total += 1
            return node

        self._update(node)
        return self._balance(node)

    def _remove(self, node, score, player_id):
        if not node:
            return None

        if score > node.score:
            node.left = self._remove(node.left, score, player_id)
        elif score < node.score:
            node.right = self._remove(node.right, score, player_id)
        else:
            if player_id in node.players:
                node.players.remove(player_id)
                node.count -= 1
                node.total -= 1
            if node.count > 0:
                self._update(node)
                return self._balance(node)
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            temp = self._min_value_node(node.right)
            node.score = temp.score
            node.players = set(temp.players)
            node.count = temp.count
            node.right = self._remove(node.right, temp.score, next(iter(temp.players)))
        self._update(node)
        return self._balance(node)

    def _min_value_node(self, node):
        current = node
        while current.left:
            current = current.left
        return current

class Leaderboard:
    def __init__(self):
        self.player_scores = {}
        self.tree = AVLTree()

    def add_score(self, player_id, new_score):
        if player_id in self.player_scores:
            old_score = self.player_scores[player_id]
            if new_score <= old_score:
                return self.get_rank(player_id)
            self.tree.root = self.tree._remove(self.tree.root, old_score, player_id)
        self.tree.root = self.tree._insert(self.tree.root, new_score, player_id)
        self.player_scores[player_id] = new_score
        return self.get_rank(player_id)

    def get_rank(self, player_id):
        score = self.player_scores.get(player_id)
        if score is None:
            return -1
        higher_count = 0
        current = self.tree.root
        while current:
            if score < current.score:
                left_total = current.left.total if current.left else 0
                higher_count += left_total + current.count
                current = current.right
            elif score > current.score:
                current = current.left
            else:
                left_total = current.left.total if current.left else 0
                higher_count += left_total
                break
        return higher_count + 1

    def get_score_by_rank(self, rank):
        if rank < 1 or not self.tree.root or rank > self.tree.root.total:
            return -1
        current = self.tree.root
        count = 0
        while current:
            left_total = current.left.total if current.left else 0
            if count + left_total >= rank:
                current = current.left
            elif count + left_total + current.count < rank:
                count += left_total + current.count
                current = current.right
            else:
                return current.score
        return -1

if __name__ == '__main__':
    leaderboard = Leaderboard()
    outputs = []
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        parts = line.split()
        cmd = parts[0]
        if cmd == 'add_score':
            player_id = int(parts[1])
            score = int(parts[2])
            outputs.append(str(leaderboard.add_score(player_id, score)))
        elif cmd == 'get_rank':
            player_id = int(parts[1])
            outputs.append(str(leaderboard.get_rank(player_id)))
        elif cmd == 'get_score_by_rank':
            rank = int(parts[1])
            outputs.append(str(leaderboard.get_score_by_rank(rank)))
    print('\n'.join(outputs))

排查方向与修复建议 #

核心问题：total字段手动维护导致的计算偏差 #

代码中手动修改total字段（如node.total +=1、node.total -=1），在树结构发生变化（如旋转、子树更新）时，容易出现与实际玩家总数不符的情况，进而导致排名计算错误。

具体修复步骤 #

1. 移除_remove中手动修改total的代码
   在_remove方法中，删除node.total -=1，依赖_update方法自动计算total：

   if player_id in node.players:
       node.players.remove(player_id)
       node.count -= 1
       # 移除 node.total -=1 这一行
   

2. 修改_insert中同分节点的更新逻辑
   在_insert方法中，删除node.total +=1，改为调用_update确保total正确：

   else:
       if player_id not in node.players:
           node.players.add(player_id)
           node.count += 1
           # 移除 node.total +=1 这一行
           self._update(node)  # 新增该行
       return node
   

3. 验证树结构与total一致性
   添加测试用例验证关键场景：

   • 多个同分玩家的排名是否共享
   • 删除最高分玩家后，剩余玩家的排名是否正确更新
   • 替换节点（删除操作触发节点替换）后，父节点的total是否正确

额外优化建议 #

• 为AVLNode添加__repr__方法，方便调试时查看节点的score、count、total值
• 单独编写单元测试，覆盖插入、删除、排名查询的各种边界场景（如空树、单节点、全同分、分数波动等）

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