数据结构复盘

数据结构用来干什么？

• 插入(包括查找插入的位置和插入这两件事)
• 查找
  • 范围查找
  • 值查找
• 删除
• 得到最大and最小
• 按序输出

学过的一些数据结构？

无序数组：干啥啥不行，可以考虑使用排序算法转换为有序数组 需要时间复杂度O(lgn)

如果是整数数组的话排序需要O(n)

BST因为不如BBST，所以不讨论了

• BBST
  • 查找合适的位置：O(lgn)
  • k检查：O(lgn) （不是只检查两个子节点就可以了！）
  • 插入：O(lgn)
  • 删除：O(lgn)
• 哈希表Chainning （假设$\alpha$ 足够小)
  • 查找合适的位置：O（1）
  • k检查：O(n)
  • 插入：O(1)
  • 删除：O(1)

小小的总结