首页 > 其他 > 详细

字典树小结

时间:2019-11-07 22:06:25      阅读:59      评论:0      收藏:0      [点我收藏+]

  1.op:插入O(N)、查找O(N)、删除

  • 时间复杂度:O(N)  N:串的长度
  • 空间复杂度:O(N*C)   N:节点个数   C:字符集大小

  2.op:插入O(N)、查找O(N)、删除

  3.ap:

  • 查询前缀,比如说判断a串是否是b串的前缀。
  • 判断一个串是否在树中出现过。

  4.优点:比较省时间,因为有26个字母,所以利用字典树可以减少查询时间。

  5.缺点:空间消耗比较大

  6.代码实现:

  • 指针(动态分配内存)
  • 指针(静态分配内存)
  • 数组模拟

字典树小结

原文:https://www.cnblogs.com/OFSHK/p/11815856.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!