AVL trees

class AVLTree:
    class Node:
        def __init__(self, key: int):
            self.key = key
            self.left = None
            self.right = None
            self.height = 1

    def __init__(self):
        self.root = None

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

    def _update(self, node):
        node.height = 1 + max(
            self._height(node.left),
            self._height(node.right),
        )

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

    def _rotate_right(self, node):
        root = node.left
        node.left = root.right
        root.right = node

        # Update the lower node before the new subtree root.
        self._update(node)
        self._update(root)
        return root

    def _rotate_left(self, node):
        root = node.right
        node.right = root.left
        root.left = node

        self._update(node)
        self._update(root)
        return root

    def _rebalance(self, node):
        self._update(node)
        balance = self._balance_factor(node)

        if balance > 1:
            # Left-right case: first convert it to left-left.
            if self._balance_factor(node.left) < 0:
                node.left = self._rotate_left(node.left)
            return self._rotate_right(node)

        if balance < -1:
            # Right-left case: first convert it to right-right.
            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, key):
        if node is None:
            return self.Node(key)

        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        else:
            # Duplicate keys are ignored.
            return node

        return self._rebalance(node)

    def insert(self, key: int) -> None:
        self.root = self._insert(self.root, key)

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

    def _delete(self, node, key):
        if node is None:
            return None

        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            if node.left is None:
                return node.right

            if node.right is None:
                return node.left

            # Replace the key with its inorder successor, then remove it.
            successor = self._min_node(node.right)
            node.key = successor.key
            node.right = self._delete(node.right, successor.key)

        return self._rebalance(node)

    def delete(self, key: int) -> None:
        self.root = self._delete(self.root, key)

    def search(self, key: int) -> bool:
        node = self.root

        while node:
            if key == node.key:
                return True

            node = node.left if key < node.key else node.right

        return False