首页 > 试题广场 >

下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是

[单选题]

下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是？

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)

```
线性表实现相对比较简单
```

平衡二叉树的各项操作的时间复杂度为O(log(n))

```
平衡二叉树的插入节点比较快
```

平衡二叉查找树

(1) 查找代价：查找效率最好，最坏情况都是O(logN)数量级的。

(2) 插入代价：总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。

(3) 删除代价：每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)

AVL 效率总结 :

查找的时间复杂度维持在O(logN)，不会出现最差情况。

AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。

AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。

发表于 2017-08-25 10:56:46 回复(0)

程序猿Go师傅

平衡二叉树插入效率为O（lgN），比哈希慢

编辑于 2019-10-21 16:55:19 回复(1)

心空在

平衡二叉树是特殊的二叉排序树，在插入节点的时候，至少需要 O(logN)。而线性表是链表的情况下只需要O(1)。

发表于 2015-09-18 22:29:03 回复(0)

想打架的蜜蜂

平衡二叉树的插入操作，可能导致树不再平衡，需要旋转

发表于 2015-08-31 22:14:21 回复(0)

__sgf__

平衡二叉树遍历操作不是O(N)吗

发表于 2022-03-22 18:05:49 回复(0)

牛客218196695号

二叉平衡树可能在插入结点后不平衡需要调整

发表于 2020-05-21 15:42:54 回复(0)

爱。在心口难开

我只想说，C选项说法有问题，各项操作的时间复杂度都为O（logn)，遍历呢？遍历不算操作？当然，就是吐槽一下，不喜勿喷

发表于 2018-07-05 21:11:49 回复(0)

Andy_Victory

在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树

发表于 2016-03-03 20:49:06 回复(0)

牛牛要炸了啊

平衡二叉树在插入新节点可能会导致失衡，需要调整节点位置关系

发表于 2022-10-22 17:36:14 回复(0)

看见我请叫我去刷题

平衡树需要被旋转调整

发表于 2022-04-19 11:43:56 回复(0)

牛客580050057号

平衡二叉查找树
(1) 查找代价：查找效率最好，最坏情况都是O(logN)数量级的。
(2) 插入代价：总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。
(3) 删除代价：每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)
AVL 效率总结 :
查找的时间复杂度维持在O(logN)，不会出现最差情况。
AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。
AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。

发表于 2021-05-12 14:16:00 回复(0)

天尊墨宇

选D

在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树

发表于 2020-06-22 09:23:22 回复(0)

许愿建行拿到offer

在平衡二叉树中插入结点要随时保持插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这棵树

发表于 2019-11-13 20:19:54 回复(0)

明石Akashi

各项操作只考虑查找插入和删除

发表于 2018-03-09 19:19:58 回复(0)

孤单的跟鞋声和你的笑丶

插入结点之后需要重新调整才行

发表于 2017-11-25 18:59:47 回复(0)

花斩

c也错的吧遍历不是O(n)？

发表于 2017-11-18 18:58:26 回复(0)

牛客717691号

平衡二叉树之一就是红黑树，插入元素难度很大，必须保证平衡

编辑于 2017-08-13 12:09:47 回复(0)

sunlight_run

平衡二叉树中插入节点，会将二叉树进行重新调整至平衡，可能需要多次旋转

发表于 2017-06-16 15:40:10 回复(0)

提交观点

问题信息

树哈希

来自：算法工程师能力评估

上传者：小海豹

难度：

29条回答 1268收藏 27297浏览