Game ranking system and red and black tree implementation

Project Introduction
This is a game website project based on the Flask framework, which includes multiple mini games (such as guessing numbers, tic toe, memory pairing, snake eating, etc.), and uses the Red and Black Tree (RBTree) data structure to achieve an efficient ranking system.
Project Features:
Using Python Flask as a backend framework

Each game maintains a ranking list independently

Storing and sorting scores using red and black tree data structure

Support score submission and ranking query

Ranking limits maximum capacity (1000 records), automatically eliminates the lowest score

Advantages of Red and Black Tree as the ranking data structure:

Efficient insertion and query operations (O(log n) time complexity)

Automatically maintain data order

Good balance to avoid performance degradation in extreme cases

Can efficiently obtain top N high-scoring players

Handwritten Red and Black Trees to realize the game ranking guide
Red and black tree basic concept
A red-black tree is a self-balancing binary search tree with the following properties:

Each node is red or black

The root node is black

Each leaf node (NIL) is black

The child node of the red node must be black

All paths from either node to each of its leaves contain the same number of black nodes

Implementation steps

1. Define node classes
   class RBNode:
   def init(self, key, value, color=RED):
   = key # sort key (score)
   = value # The stored value (player name)
   = color # node color
   = None # left child node
   = None # Right child node
   = None # Parent node

2. Implement the basic structure of red and black trees
   class RBTree:
   def init(self):
   = RBNode(None, None, BLACK) # Sentry node
   = # Initially the root node points to the sentry

3. Implement the insertion operation
   Insertion is divided into two steps:
   Normal binary search tree insertion
   Repair the properties of red and black trees
   def insert(self, key, value):

   Create a new node (default is red)

   new_node = RBNode(key, value)
   new_node.left =
   new_node.right =

   Normal BST insertion

   parent = None
   current =
   while current != :
   parent = current
   if key < :
   current =
   else:
   current =

   Set the parent node of the new node

   new_node.parent = parent

   Update the parent node's child node's reference

   if parent is None:
   = new_node
   elif key < :
   = new_node
   else:
   = new_node

   Repair the properties of red and black trees

   self._fix_insert(new_node)

4. Implement insert repair
   The nature of the red and black tree may be violated after insertion and needs to be fixed by rotation and recoloring:
   def _fix_insert(self, node):
   while == RED:
   # The parent node is the right child of the grandfather
   if == :
   uncle =
   if == RED:
   # Case 1: The uncle node is red
   = BLACK
   = BLACK
   = RED
   node =
   else:
   if node == :
   # Case 2: The uncle node is black and the current node is the left child node
   node =
   self._right_rotate(node)
   # Case 3: The uncle node is black and the current node is the right child node
   = BLACK
   = RED
   self._left_rotate()
   else:
   # Symmetrical situation
   uncle =
   if == RED:
   = BLACK
   = BLACK
   = RED
   node =
   else:
   if node == :
   node =
   self._left_rotate(node)
   = BLACK
   = RED
   self._right_rotate()

    if node == :
        break
   

   = BLACK

5. Implement rotation operation
   Rotation is the key operation to maintain red and black tree balance:
   def _left_rotate(self, x):
   y =
   =
   if != :
   = x

   =
   if is None:
   = y
   elif x == :
   = y
   else:
   = y

   = x
   = y

def _right_rotate(self, x):
y =
=
if != :
= x

 = 
if  is None:
     = y
elif x == :
     = y
else:
     = y

 = x
 = y

6. Implement ranking function
   def get_top_scores(self, n):
   """Get the first n highest scores"""
   result = []
   self._reverse_inorder(, result, n)
   return result

def _reverse_inorder(self, node, result, limit):
if node == or len(result) >= limit:
return

# traverse the right subtree first (larger value)
 self._reverse_inorder(, result, limit)

 if len(result) < limit:
     ((, ))

 # traverse the left subtree again (smaller value)
 self._reverse_inorder(, result, limit)

Summarize
Implement the game ranking system through handwritten red and black trees:
Efficient score insertion and query performance
Automatic maintenance score sorting
You can easily get the top N players
High memory usage efficiency
This implementation is particularly suitable for game application scenarios that require frequent updates and query rankings, and can ensure that good performance is maintained under the large amount of data.