《数据结构(Java版)(第2版)》
4.二叉排序树的删除二叉排序树的删除
《数据结构(Java版)(第2版)》
5.二叉排序树的查找性能分析二叉排序树的查找性能分析
211ASL成功=∑(pi×ci)=(1×1+2×2+3×4+4×1)==2.62588i=1
n
ASL成功
n+18+11n=∑i===4.5ni=122
《数据结构(Java版)(第2版)》
8.3.2平衡二叉树
《数据结构(Java版)(第2版)》
8.4散列
8.4.18.4.28.4.38.4.4散列表散列函数处理冲突构造链地址法的散列表
《数据结构(Java版)(第2版)》
8.4.1散列表
1.2.
散列函数
i=hash(key)
冲突
k1≠k2
hash(k1)=hash(k2)
《数据结构(Java版)(第2版)》
8.4.2散列函数
1.2.3.
除留余数法
hash(k)=k%p
平方取中法折叠法
《数据结构(Java版)(第2版)》
8.4.3处理冲突
1.2.
开放定址法链地址法
ASL成功
6×1+2×2+3×2==1.610
《数据结构(Java版)(第2版)》
8.4.4构造链地址法的散列表
《数据结构(Java版)(第2版)》