Реализовать AVL-балансировку дерева поиска, которое хранит значения только в листьях

задача: реализовать словарь на основе AVL-сбалансированного дерева поиска, в котором данные хранятся в листьях.

Я написал класс-словарь: дерево поиска, с AVL-балансировкой, в котором значения хранятся в узлах. Как правильно исправить, чтобы значения сохранялись только в листьях? Буду признателен за любую помощь. Если значения в узле нет, то обычно ключ в узле -- это наименьший из ключей правого поддерева (или что угодно другое, разделяющее ключи левого и ключи правого поддерева)

class Node:
    def __init__(self, key, value=None, left=None, right=None, inv=False):
        if inv:
            left, right = right, left
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        self.exist = 1
        if left is not None and right is not None:
            self.height = 1 + max(self.left.height, self.right.height)
        elif left is not None:
            self.height = 1 + self.left.height
        elif right is not None:
            self.height = 1 + self.right.height
        else:
            self.height = 1


class Dict:
    def __init__(self):
        self.root = None
        self.len = 0

    def __len__(self):
        return self.len

    def __getitem__(self, key):
        if not self.root:
            raise KeyError()
        else:
            return self.get(self.root, key)

    def __contains__(self, key):
        try:
            self.__getitem__(self.root, key)
            return True
        except:
            return False

    def __setitem__(self, key, value):
        if not self.root:
            self.root = Node(key, value)
        else:
            self.root = self.put(self.root, key, value)
        self.len += 1

    def __delitem__(self, key):
        if key not in self:
            raise KeyError()
        else:
            self.delete(self.root, key)
        self.len -= 1

    def delete(self, tree, key):
        if key == tree.key:
            tree.exist = 0
            return
        return self.delete(self.children(tree, key < tree.key)[1], key)

    def height(self, tree): return 0 if tree is None else tree.height

    def children(self, tree, inv): return (tree.right, tree.left) if inv else (tree.left, tree.right)

    def reassoc(self, tree, inv):
        l, r = self.children(tree, inv)
        rl, rr = self.children(r, inv)
        return Node(r.key, r.value, Node(tree.key, tree.value, l, rl, inv), rr, inv)

    def avl(self, tree, inv):
        l, r = self.children(tree, inv)
        if self.height(r) - self.height(l) < 2:
            return tree
        rl, rr = self.children(r, inv)
        if self.height(rl) - self.height(rr) == 1:
            r = self.reassoc(r, not inv)
        return self.reassoc(Node(tree.key, tree.value, l, r, inv), inv)

    def put(self, tree, key, value):
        if tree is None:
            return Node(key, value, None, None)
        if tree.key == key:
            self.len -= 1
            if tree.exist==0:self.len+=1
            return Node(key, value, tree.left, tree.right)
        inv = key < tree.key
        left, right = self.children(tree, inv)
        return self.avl(Node(tree.key, tree.value, left,
                        self.put(right, key, value), inv), inv)

    def get(self, tree, key):
        if tree is None:
            raise KeyError()
        if key == tree.key and tree.exist == 0:
            raise KeyError()
        elif key == tree.key and tree.exist != 0:
            return tree.value
        return self.get(self.children(tree, key < tree.key)[1], key)