【读书笔记】数据结构与算法分析 - C 语言描述 - 第四部分 - 搜索

   25 min read

第十二章 符号表和二叉搜索树

插入搜索选择插入搜索命中搜索失败
最坏平均
关键字索引数组11M111
有序数组NN1N/2N/2N/2
有序链表NNNN/2N/2N/2
无序数组1NNlgN1N/2N
无序链表1NNlgN1N/2N
二分搜索NlgN1N/2lgNlgN
二叉搜索树NNNlgNlgNlgN
红黑树lgNlgNlgNlgNlgNlgN
随机树N*N*N*lgNlgNlgN
散列1N*NlgN111

第十三章 平衡树

第十四章 散列

第十五章 基数搜索

第十六章 外部搜索