最近遇到和看到的一些面试题。

我知道你大学毕业过后就没接触过算法数据结构了,但是请你一定告诉我什么是Binary search tree? search的时间复杂度是多少?

Binary search tree 二叉搜索树主要由四个方法:

  • search: 时间复杂度为O(h),h为树的高度
  • traversal: 时间复杂度为O(n),n为树的总结点数。
  • insert: 时间复杂度为O(h),h为树的高度。
  • delete: 最坏情况下,时间复杂度为O(h)+指针的移动开销。

可以看到,二叉搜索树的dictionary operation的时间复杂度与树的高度h相关。所以需要尽可能的降低树的高度,由此引出平衡二叉树Balanced binary tree。它要求左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这样就可以将搜索树的高度尽量减小。常用算法有 红黑树AVLTreap伸展树等。