首页 > 试题广场 >

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

[单选题]

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

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

心空在

平衡二叉树是特殊的二叉排序树，在插入节点的时候，至少需要 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)

Engic

选项C的说法有问题：啥叫“平衡二叉树的各项操作的时间复杂度为O(log(n))”，啥叫“各项操作”？把整棵树所有节点都处理一遍的操作怎么可能时间复杂度还是这么小呢？又没限制只能是查找插入删除这样的操作。

发表于 2024-10-27 06:59:17 回复(0)

爱吃香菜的做题家许愿简历通过

我认为结点的关键是一定是不同的，所以A选项没错

发表于 2024-07-21 14:56:13 回复(0)

Xiao_Cow

平衡二叉树中插入节点需要确保插入后二叉树是平衡的，故常还需要做树旋转，并不是很快

发表于 2024-06-25 20:56:10 回复(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)

提交观点

问题信息

树哈希

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

上传者：小海豹

难度：

32条回答 1294收藏 27523浏览