Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/tutosrive/avl_tree_car/llms.txt

Use this file to discover all available pages before exploring further.

The AVL tree is the central data structure of this backend. Because every insert, search, and delete runs in O(log n) — guaranteed by the self-balancing property — the server can keep road obstacles sorted by their x-coordinate and answer traversal queries efficiently regardless of how many obstacles are loaded. Without rebalancing, a degenerate insertion order (e.g., obstacles added left-to-right) would degrade the tree to a linked list with O(n) operations; the AVL rotations prevent that by keeping the tree height within ⌈log₂(n+1)⌉.
Every insert and delete in an AVL tree is guaranteed O(log n) time. This means the backend can handle hundreds of obstacles per simulation run without any noticeable slowdown in traversal or lookup.

​
Height and Balance Factor

Each Node stores an integer height that is updated after every structural change. The height of a node is defined as: 
node.height = 1 + max(height(left), height(right))
A missing child (i.e., None) has an implicit height of 0. The balance factor (BF) of a node measures how skewed its two subtrees are: 
BF = height(left) - height(right)
A valid AVL node has a BF of -1, 0, or 1. Any value outside that range means the tree is unbalanced at that node and a rotation must be applied. The two helpers that implement this in tree.py are: 
def get_height(self, node: Node):
    return node.height if node else 0

def update_height(self, node: Node):
    # Is 1+max(left, right), because is UPDATE, means that I add new node
    # Ever height is UP (+)
    if node:
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

def get_balance_factor(self, node: Node):
    # BALANCE FACTOR = BF
    # BF = (HEIGHT-LEFT-SIDE) - (HEIGHT-RIGHT-SIDE)
    # BF == OK, when BF is in range [-1, 0, 1]
    # Other out range is BAD
    # If don't exists node BF = 0
    return self.get_height(node.left) - self.get_height(node.right) if node else 0

​
Rotations

When _rebalance detects a BF outside [-1, 0, 1] it applies one of four rotation patterns. The table below summarises the trigger conditions:
CaseTriggerSub-triggerFix
LL (Right rotation)BF > 1Left child BF >= 0_rotate_right(node)
LR (Left-Right)BF > 1Left child BF < 0_rotate_left(node.left) then _rotate_right(node)
RR (Left rotation)BF < -1Right child BF <= 0_rotate_left(node)
RL (Right-Left)BF < -1Right child BF > 0_rotate_right(node.right) then _rotate_left(node)
The dispatcher method that selects among these cases is _rebalance: 
def _rebalance(self, node: Node) -> Node:
    """Balance the AVL tree"""
    if not node:
        return node

    balance_factor = self.get_balance_factor(node)

    # Left Heavy (L)
    if balance_factor > 1:
        # Case LR (Left-Right)
        if self.get_balance_factor(node.left) < 0:
            node.left = self._rotate_left(node.left)

        # Just the L rotation
        return self._rotate_right(node)

    # Right Heavy (R)
    if balance_factor < -1:
        # Case RL (Right-Left)
        if self.get_balance_factor(node.right) > 0:
            node.right = self._rotate_right(node.right)

        # Just the R rotation
        return self._rotate_left(node)

    return node

​
Right rotation (_rotate_right) — used in LL and LR

A right rotation promotes the left child as the new subtree root, moving the old root down to become the right child of the new root. The old root’s left pointer is updated to hold the new root’s former right subtree (subtree). 
def _rotate_right(self, old_root: Node) -> Node:
    """Right rotation and update parents"""
    new_root: Node = old_root.left
    subtree: Node = new_root.right

    # Rotate
    new_root.right = old_root
    old_root.left = subtree

    # Update parents
    new_root.parent = old_root.parent
    old_root.parent = new_root
    if subtree:
        subtree.parent = old_root

    # Update nodes height
    self.update_height(old_root)
    self.update_height(new_root)

    return new_root

​
Left rotation (_rotate_left) — used in RR and RL

A left rotation is the mirror image: the right child becomes the new root and the old root becomes its left child. The old root’s right pointer receives the new root’s former left subtree. 
def _rotate_left(self, old_root: Node) -> Node:
    """Left Rotation"""
    new_root: Node = old_root.right
    subtree: Node = new_root.left

    # Rotate
    new_root.left = old_root
    old_root.right = subtree

    # Update parents
    new_root.parent = old_root.parent
    old_root.parent = new_root
    if subtree:
        subtree.parent = old_root

    # Update heights
    self.update_height(old_root)
    self.update_height(new_root)

    return new_root

​
Insertion

Obstacles are keyed by their x coordinate during traversal. The public insert method first calls search to check for an existing node at the same (x, y) coordinates. If a duplicate is found, the insert is rejected immediately. Otherwise a new Node wraps the Obstacle and is threaded into the tree recursively, with _rebalance called on every node on the way back up the call stack. 
def insert(self, value: Obstacle) -> ReturnModels:
    node: ReturnModels = self.search(value)
    response: ReturnModels = ReturnModels(f'The node with coordinates ({value.x}, {value.y}) has been added successfully!')

    # not None = node...
    if node.data:
        response.ok = False
        response.message = f'Node with coordinates ({value.x}, {value.y}) already exists.'
    else:
        new_node: Node = Node(value)
        if not self.root:
            self.root = new_node
        else:
            self.root = self._insert(self.root, new_node)

        # Add the obstacle ID, requires more next
        response.data = new_node.value.id
    return response
The recursive helper _insert descends left when new_node.value.x < current_node.value.x and right otherwise. After placing the node, it calls update_height then _rebalance before returning, propagating any rotation result up the chain: 
def _insert(self, current_node: Node, new_node: Node) -> Node:
    if current_node:
        if new_node.value.x < current_node.value.x:
            if not current_node.left:
                current_node.left = new_node
                new_node.parent = current_node
            else:
                current_node.left = self._insert(current_node.left, new_node)
        else:
            if not current_node.right:
                current_node.right = new_node
                new_node.parent = current_node
            else:
                current_node.right = self._insert(current_node.right, new_node)

    # Update the currentNode height
    self.update_height(current_node)

    # Balance the currentNode and return if have any rotation
    return self._rebalance(current_node)

​
Deletion

Deletion covers three structural cases. After any case, _rebalance_up walks back toward the root re-balancing every ancestor of the removed node. Case 1 — Leaf node: No children. The node is simply unlinked from its parent via changeNodePosition(node, None), then _rebalance_up is called from the parent. Case 2 — Two children: The node is replaced by its inorder predecessor — the rightmost node in the left subtree. The predecessor is found by _getPredecessor: 
def _getPredecessor(self, node: Node) -> Node | None:
    if node.left:
        current: Node = node.left
        while current.right:
            current = current.right
        return current
    return None
Two sub-cases arise depending on whether the predecessor is a direct left child or deeper in the subtree. In both, the predecessor takes the deleted node’s position and _rebalance_up is triggered from the predecessor’s original parent. Case 3 — One child: The single child slides up to replace the deleted node; _rebalance_up is called from the old parent. _rebalance_up iterates from the given start node to the root, updating heights and applying _rebalance at each step. If a rotation changes the subtree root, the parent’s child pointer is updated before continuing upward.

​
Traversals

All three traversals return a ReturnModels object whose data field is a flat list of Obstacle instances.

Inorder

left → root → rightVisits nodes in ascending order of x coordinate. The frontend uses this traversal to get obstacles ordered by their road position.

Preorder

root → left → rightVisits the root before its subtrees. Useful for reconstructing the exact tree shape from a serialised list.

Posorder

left → right → rootVisits children before the parent. Each traversal result can be streamed obstacle-by-obstacle to the frontend over Socket.IO.
All three share the same internal structure. Here is the inorder implementation as a representative example: 
def inorder(self):
    response = ReturnModels()
    if not self.root:
        response.message = "Don't was possible get road"
        response.error = 'Tree is empty!'
    else:
        road = []
        response.data = self.__inorder(self.root, road)

    return response

def __inorder(self, current_node: Node, road: list[int]):
    if current_node:
        if current_node.left:
            self.__inorder(current_node.left, road)

        road.append(current_node.value)

        if current_node.right:
            self.__inorder(current_node.right, road)

        return road

​
Tree Serialization

AVLTree.to_dict() delegates to Utils.extract_tree_childs(self.root). The utility recursively walks the tree and builds a nested dictionary where each node is represented by its obstacle’s id string, plus an optional children array containing serialized left and right subtrees (only present when children exist): 
def to_dict(self):
    return Utils.extract_tree_childs(self.root)

# From others_utils.py
@classmethod
def extract_tree_childs(cls, tree: Node) -> dict | None:
    def wrapper(current: Node):
        __response: dict | None = None
        if current:
            __response = {'id': current.value.id}

            childs = []

            if current.left:
                childs.append(wrapper(current.left))
            if current.right:
                childs.append(wrapper(current.right))

            if len(childs) > 0:
                __response['children'] = childs

        return __response
    return wrapper(tree)
A serialized tree with three nodes looks like this: 
{
  "id": "0A2B4C6D",
  "children": [
    { "id": "1X3Y5Z7W" },
    {
      "id": "2Q4R6S8T",
      "children": [
        { "id": "3M5N7P9K" }
      ]
    }
  ]
}

Build docs developers (and LLMs) love

Get started for freeTalk to us