首页 > 试题广场 >

对以下各搜索树进行删除操作,哪些树在最坏情况下时间复杂度不超

[不定项选择题]

对以下各搜索树进行删除操作,哪些树在最坏情况下时间复杂度不超过O(log(n))?其中n为关键码的数量。 

  • AVL 树
  • 伸展树
  • 红黑树
  • 二叉查找树
只要保证树是平衡的就可以满足最坏时间复杂度不超过O(logn),即AVL树和红黑树。B和D都属于二叉排序树,因此有可能得到O(n)的时间复杂度。
发表于 2021-01-04 12:01:57 回复(0)
A. AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)
B.伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。伸展树支持所有的二叉树操作。伸展树不保证最坏情况下的时间复杂度为O(logN)。伸展树的时间复杂度边界是均摊的
C.红黑树(Red Black Tree) 是一种自平衡二叉查找树,它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的 是树中元素的数目。
D.在二叉查找树中查询元素的最优时间复杂度是O(logN)即在满二叉树的情况下,最坏时间复杂度是O(n)即除叶子节点外每个节点只有一个子节点,
发表于 2019-07-10 16:25:51 回复(0)