面试题库 › C++ / 后端 › 二叉搜索树的插入与复杂度

二叉搜索树的插入与复杂度

难度 ★☆☆在 6 场真实面经中被问到 方向:C++ / 后端考点:树与二叉树

哪些公司问过

腾讯1阿里巴巴1vivo1顺丰同城科技1多家公司(猿辅导、百度、网易互娱、滴滴、锐捷网络、吉比特、亿联网络等)1

常见岗位:Java 后端、NLP / 语音、C++ 后端、C++ / Qt 客户端、C/C++ 软件开发

答案要点

  1. BST 性质:左子树节点都小于根,右子树节点都大于根
  2. 插入:从根开始比较,小于往左、大于往右,走到空位创建新节点
  3. 递归和迭代均可;迭代需要记录父节点
  4. 要事先约定重复值策略:忽略、放右侧或计数
  5. 时间平均 O(log n),最坏 O(n);需要平衡用 AVL 或红黑树

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题