思考？

在 n 个动态的整数中搜索某个整数？ (查看其是否存在)

  • 假设用动态数组存放元素，从第0个位置开始遍历搜索，平均时间复杂度 O(N)
  • 如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度 O(log N)
    • 但是添加，删除的平均时间复杂度是 O(N)
  • 针对这个需求， 有没有更好的方案？
    • 使用二叉搜索树，添加/删除/搜索的最坏时间复杂度均可优化至 O(log N)

定义：

二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称 BST ，又被称为：二叉查找树，二叉排序树

  • 任意节点的值都 大于 其左子树的节点的值
  • 任意节点的值都 小于 其右子树节点的值
  • 它的左右子树也是一棵二叉搜索树

二叉搜索树可以大大提高搜索数据的效率

二叉搜索树存储的元素必须具备可比较性

  • 比如int , double类型

  • 如果是自定义类型，需要指定比较方式

  • 不允许为 null