Python, Бинарное дерево, поиск и удаление элементов по их id

Приходят различные пары значений, первый элемент пары- просто float, второй элемент- уникальный id пары. Необходимо уметь динамически сортировать большой набор пар (в течение работы программы будут приходить новые пары), находить id пары с минимальным значением, удалять пары по их id. Предлагаемое решение- бинарное дерево. В узлах хранятся ссылки на правые и левые подветви, значение value (первый элемент приходящей пары) и id узла (второй элемент приходящей пары).

class Node:
    def __init__(self, value, node_id, parent=None, child_l=None, child_r=None):
        self.node_id = node_id
        self.value = value
        self.parent = parent
        self.child_l = child_l
        self.child_r = child_r


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

    def add(self, val, node_id):
        if self.root:
            self._add(val, node_id, self.root)
        else:
            self.root = Node(val, node_id)

    def _add(self, val, node_id, node):
        if val < node.value:
            if node.child_l:
                self._add(val, node_id, node.child_l)
            else:
                node.child_l = Node(val, node_id,  parent=node)
                self.min = node.child_l
        else:
            if node.child_r:
                self._add(val, node_id, node.child_r)
            else:
                node.child_r = Node(val, node_id, parent=node)

    def get_min(self):
        return self._get_min(self.root).value

    def _get_min(self, node):
        if node.child_l:
            return self._get_min(node.child_l)
        else:
            return node

    def delete_node(self, node_id):
        self._delete_node(node_id, self.root)

    def _delete_node(self, node_id, root):
        if root.node_id != node_id:
            if root.child_l:
                self._delete_node(node_id, root.child_l)
            if root.child_r:
                self._delete_node(node_id, root.child_r)
        else:
            if root.child_l and root.child_r:
                min_right_subtree = self._get_min(root.child_r)
                root.node_id = min_right_subtree.node_id
                root.value = min_right_subtree.value
                min_right_subtree = None
            elif root.child_l and not root.child_r:
                root.node_id = root.child_l.node_id
                root.value = root.child_l.value
                if root.child_l.child_l:
                    root.child_l = root.child_l.child_l
                if root.child_l.child_r:
                    root.child_r = root.child_l.child_r
                root.child_l.parent = None
            elif not root.child_l and root.child_r:
                root.node_id = root.child_r.node_id
                root.value = root.child_r.value
                if root.child_r.child_l:
                    root.child_l = root.child_r.child_l
                if root.child_r.child_r:
                    root.child_r = root.child_r.child_r
                root.child_r.parent = None
            else:
                root = None

Если динамическая сортировка и поиск минимума в такой конфигурации дерева выполняются достаточно быстро (могу еще ввести какой нить алгоритм балансировки), то вот удаление элементов по id совсем медленно работает, и понятно почему- необходимо обходить все дерево целиком при поиске узла с подходящим id. Есть ли варианты обойти эту проблему? id могут быть любым типом данных, string, float, int, tuple, главное что он гарантировано уникален для всех узлов.