Python数据结构.docx

Python数据结构全文共9页，当前为第1页。Python数据结构全文共9页，当前为第1页。1 红黑树 Python数据结构全文共9页，当前为第1页。 Python数据结构全文共9页，当前为第1页。 红黑树与AVL的比较： AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多； 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低； 所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。 编程题 1 台阶问题/斐波纳挈 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2) 第二种记忆方法 def memo(func): cache = {} def wrap(*args): if args not in cache: cache[args] = func(*args) return cache[args] return wrap @