如何基于AVL树实现Python自定义字典，满足指定接口与性能要求

实现要求 #

• 采用AVL树实现字典类型，所有put/get/in/del操作均达到对数级时间复杂度
• 基于给定的TreeNode和mydict类定义完成实现，至少覆盖所有预置的接口方法
• key类型至少支持整数、浮点数、字符串三类
• 需调用hash(key)作为AVL树的节点键值用于排序
• __str__、keys、values方法的输出顺序为AVL树的LDR（左子树、根、右子树）中序遍历顺序
• 输出按hash(key)排序，与Python 3.7及以上版本内置字典的插入顺序输出逻辑不同

初始代码框架 #

class TreeNode:
    """
    Binary tree nodes
    Please complete the internal implementation of the node by yourself and implement the given interface
    """
    def __init__(self, key, val=None):  
        pass

    def getLeft(self):  # Get the left subtree (return None if it does not exist)
        pass

    def getRight(self):  # Get the right subtree (return None if it does not exist)
        pass


class mydict:
    """
    Implementing dictionary types using AVL trees
    """
    def getRoot(self):  # Return the internal AVL tree root
        pass

    def __init__(self):  # Create an empty dictionary
        pass

    def __setitem__(self, key, value):  # Save key:value to dictionary
        # md[key]=value
        pass

    def __getitem__(self, key):  # Get the value from the dictionary based on the key
        # v = md[key]
        # If the key does not exist in the dictionary, please raise KeyError
        pass

    def __delitem__(self, key):  # Delete the key from the dictionary
        # del md[key]
        # If the key does not exist in the dictionary, please raise KeyError
        pass

    def __len__(self):  # Get the length of the dictionary
        # l = len(md)
        pass

    def __contains__(self, key):  # Determine if a key exists in the dictionary
        # k in md
        pass

    def clear(self):  # remove dict
        pass

    def __str__(self):  # Output string form, refer to the built-in dict type, output according to the AVL tree LDR traversal
        # print type：{'name': 'sessdsa', 'hello': 'world'}
        pass

    __repr__ = __str__

    def keys(self):  # Return all values, type is a list, in the order of AVL tree LDR traversal
        pass

    def values(self):  # Return all values, type is a list, in the order of AVL tree LDR traversal
        pass

完整可运行实现代码 #

class TreeNode:
    """
    二叉树节点类
    """
    def __init__(self, key, val=None):
        self.key = key
        self.val = val
        self.hash_key = hash(key)
        self.left = None
        self.right = None
        self.height = 1  # 叶子节点初始高度为1

    def getLeft(self):
        return self.left

    def getRight(self):
        return self.right


class mydict:
    """
    基于AVL树实现的字典类
    """
    def getRoot(self):
        return self.root

    def __init__(self):
        self.root = None
        self.size = 0

    # 辅助方法：获取节点高度
    def _get_height(self, node):
        if not node:
            return 0
        return node.height

    # 辅助方法：更新节点高度
    def _update_height(self, node):
        if not node:
            return
        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

    # 辅助方法：获取平衡因子
    def _get_balance(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    # 右旋操作
    def _rotate_right(self, z):
        y = z.left
        T3 = y.right

        # 旋转
        y.right = z
        z.left = T3

        # 更新高度
        self._update_height(z)
        self._update_height(y)

        return y

    # 左旋操作
    def _rotate_left(self, z):
        y = z.right
        T2 = y.left

        # 旋转
        y.left = z
        z.right = T2

        # 更新高度
        self._update_height(z)
        self._update_height(y)

        return y

    # 辅助方法：插入节点
    def _insert_node(self, node, key, val):
        # 标准BST插入
        if not node:
            self.size +=1
            return TreeNode(key, val)
        key_hash = hash(key)
        if key_hash < node.hash_key:
            node.left = self._insert_node(node.left, key, val)
        elif key_hash > node.hash_key:
            node.right = self._insert_node(node.right, key, val)
        else:
            # hash相同，判断key是否相等
            if key == node.key:
                node.val = val
                return node
            else:
                # 处理hash冲突，约定存入右子树
                node.right = self._insert_node(node.right, key, val)

        # 更新当前节点高度
        self._update_height(node)

        # 获取平衡因子判断是否失衡
        balance = self._get_balance(node)

        # 左左情况
        if balance > 1 and key_hash < node.left.hash_key:
            return self._rotate_right(node)

        # 右右情况
        if balance < -1 and key_hash > node.right.hash_key:
            return self._rotate_left(node)

        # 左右情况
        if balance > 1 and key_hash > node.left.hash_key:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)

        # 右左情况
        if balance < -1 and key_hash < node.right.hash_key:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

    def __setitem__(self, key, value):
        self.root = self._insert_node(self.root, key, value)

    # 辅助方法：查找节点
    def _search_node(self, node, key):
        if not node:
            return None
        key_hash = hash(key)
        if key_hash < node.hash_key:
            return self._search_node(node.left, key)
        elif key_hash > node.hash_key:
            return self._search_node(node.right, key)
        else:
            if key == node.key:
                return node
            else:
                # hash冲突时去右子树查找
                return self._search_node(node.right, key)

    def __getitem__(self, key):
        node = self._search_node(self.root, key)
        if not node:
            raise KeyError(key)
        return node.val

    # 辅助方法：找子树最小节点
    def _get_min_node(self, node):
        if node is None or node.left is None:
            return node
        return self._get_min_node(node.left)

    # 辅助方法：删除节点
    def _delete_node(self, node, key):
        if not node:
            return node
        key_hash = hash(key)
        if key_hash < node.hash_key:
            node.left = self._delete_node(node.left, key)
        elif key_hash > node.hash_key:
            node.right = self._delete_node(node.right, key)
        else:
            if key != node.key:
                node.right = self._delete_node(node.right, key)
            else:
                # 找到待删除节点
                if node.left is None:
                    temp = node.right
                    node = None
                    self.size -=1
                    return temp
                elif node.right is None:
                    temp = node.left
                    node = None
                    self.size -=1
                    return temp
                # 有两个子节点的情况
                temp = self._get_min_node(node.right)
                node.key = temp.key
                node.val = temp.val
                node.hash_key = temp.hash_key
                node.right = self._delete_node(node.right, temp.key)

        if node is None:
            return node

        # 更新高度
        self._update_height(node)

        # 计算平衡因子
        balance = self._get_balance(node)

        # 左左失衡
        if balance > 1 and self._get_balance(node.left) >=0:
            return self._rotate_right(node)

        # 左右失衡
        if balance >1 and self._get_balance(node.left) <0:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)

        # 右右失衡
        if balance < -1 and self._get_balance(node.right) <=0:
            return self._rotate_left(node)

        # 右左失衡
        if balance < -1 and self._get_balance(node.right) >0:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

    def __delitem__(self, key):
        if key not in self:
            raise KeyError(key)
        self.root = self._delete_node(self.root, key)

    def __len__(self):
        return self.size

    def __contains__(self, key):
        return self._search_node(self.root, key) is not None

    def clear(self):
        self.root = None
        self.size =0

    # 辅助方法：中序遍历
    def _ldr_traverse(self, node, res):
        if not node:
            return
        self._ldr_traverse(node.left, res)
        res.append((node.key, node.val))
        self._ldr_traverse(node.right, res)

    def __str__(self):
        items = []
        self._ldr_traverse(self.root, items)
        item_str = ', '.join([f"{repr(k)}: {repr(v)}" for k,v in items])
        return "{" + item_str + "}"

    __repr__ = __str__

    def keys(self):
        items = []
        self._ldr_traverse(self.root, items)
        return [k for k,v in items]

    def values(self):
        items = []
        self._ldr_traverse(self.root, items)
        return [v for k,v in items]


# 测试用例
if __name__ == "__main__":
    print("=========  Implementing dictionary types using AVL trees ==========")
    md = mydict()
    md['hello'] = 'world'
    md['name'] = 'sessdsa'
    print(md)  # 输出顺序由hash值排序决定，与插入顺序无关

    for f in range(1000):
        md[f**0.5] = f

    for i in range(1000, 2000):
        md[i] = i**2

    print(len(md))  # 2002
    print(md[2.0])  # 4
    print(md[1000])  # 1000000
    print(md['hello'])  # world
    print(20.0 in md)  # True
    print(99 in md)  # False

    del md['hello']
    print('hello' in md)  # False
    for i in range(1000, 2000):
        del md[i]
    print(len(md))  # 1001
    for f in range(1000):
        del md[f**0.5]
    print(len(md))  # 1
    print(md.keys())  # ['name']
    print(md.values())  # ['sessdsa']
    for a in md.keys():
        print(md[a])  # sessdsa
    md.clear()
    print(md)  # {}

内容的提问来源于stack exchange，提问作者Guming