时间戳

首页 > 解决方案 > 如何用 AVL 树实现字典？

python - 如何用 AVL 树实现字典？

问题描述

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)

    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


# code end

#mydict=dict
print("=========  Implementing dictionary types using AVL trees =========")
md = mydict()
md['hello'] = 'world'
md['name'] = 'sessdsa'
print(md)  # {'name': 'sessdsa', 'hello': 'world'}

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)  # {}

我不知道如何用 AVL 树实现 dict。

---- 使用 AVL 树实现字典类型 ----

  1. 使用 AVL 树实现字典类型以实现所有 put/get/in/del 操作的对数性能
  2. 使用以下类定义至少实现以下方法
  3. key 至少支持整数、浮点数、字符串
  4. 请调用 hash(key) 作为 AVL 树的节点键
  5. 注意__str__，keys,values 方法的输出顺序是LDR(leftchild, data, rightchild)AVL 树遍历顺序的。
  6. 也就是按照hash(key)来排序，这和Python 3.7的dict输出顺序不一样。

标签： pythondictionary

解决方案

我建议您看一下“使用 Python 使用算法和数据结构解决问题”一书。它为您提供了主要数据结构的理论信息和实现。

第 7 章是关于树的所有内容，并包含实现 AVL 所需的所有细节。

推荐阅读