首页 > 试题广场 >

给定n个节点的平衡二叉搜索树,每个节点的值是整数。给定一个整

[单选题]
给定n个节点的平衡二叉搜索树,每个节点的值是整数。给定一个整数,在树中找出与该整数最接近的节点的最小算法复杂度是()
  • Θ(logn)
  • Θ(n^2)
  • Θ(nlogn)
  • Θ(n)
  • Θ(1)
  • Θ(n!)
对于任何一个节点n,他的上一个元素必然是它或者他的父节点或者更父节点的左子树的最右节点,下一个元素是他右子树或者父节点右子树或者更父节点的右子树的最左节点,无论怎样,查找一个子树最左或者最右节点的平均复杂度都是树高,即O(logn)
发表于 2022-07-03 10:08:04 回复(0)