关于红黑树和AVL树，以下哪种说法不正确？_

Amour1018

红黑树和avl树都属于自平衡二叉树；

两者查找、插入、删除的时间复杂度相同；

包含n个内部结点的红黑树的高度是o(logn);

TreeMap是一个红黑树的实现，能保证插入的值保证排序

发表于 2015-10-03 11:12:14 回复(1)

黄小斜

红黑树和avl树都属于自平衡二叉树；

两者查找、插入、删除的时间复杂度相同；

包含n个内部结点的红黑树的高度是o(logn);

TreeMap是一个红黑树的实现，能保证插入的值保证排序

发表于 2017-04-03 18:38:09 回复(0)

牛客栗子号

明明是单选题, 非要伪装成多选题的样子

发表于 2020-06-17 11:48:01 回复(0)

凯Kai4

红黑树和AVL 二叉树都是自平衡二叉树。AVL二叉树是完全平衡二叉树，它的左右节点都是AVL二叉树，且节点的高度差不大于1。红黑树不追求完全平衡，从而降低旋转的次数。

发表于 2018-09-14 15:16:23 回复(0)

yayamma

关于红黑树和AVL树，来自网络：

1 好处及用途

红黑树 并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

红黑树能够以 O(log₂ n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。

在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。

典型的用途是实现关联数组

2 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.

AVL树的定义:
一棵AVL树满足以下的条件:
1>它的左子树和右子树都是AVL树
2>左子树和右子树的高度差不能超过1
从条件1可能看出是个递归定义,如GNU一样.

性质:
1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)
2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

从1这点来看 红黑树是牺牲了严格的高度平衡的优越条件 为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

发表于 2015-09-09 15:11:16 回复(2)

Huzi在路上

C:包含n个内部结点的红黑树树高应为至少 O(log(n))。C答案的描述并不准确。

发表于 2016-05-24 16:18:41 回复(1)

TTT爱吃糖

啥叫自平衡二叉树？

发表于 2018-10-01 17:38:42 回复(0)

givemeoffer

本来 lm

发表于 2018-03-17 17:51:14 回复(0)

sgbs

要死了要死了 JDK指啥？

发表于 2017-06-10 13:40:11 回复(5)

不思进取的我

完全避开了正确答案。。

发表于 2017-02-26 13:50:08 回复(0)

细雨湿身

关于红黑树和AVL树，来自网络：

1 好处及用途

红黑树并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

红黑树能够以 O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。

在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。

典型的用途是实现关联数组

2 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.

AVL树的定义:
一棵AVL树满足以下的条件:
1>它的左子树和右子树都是AVL树
2>左子树和右子树的高度差不能超过1
从条件1可能看出是个递归定义,如GNU一样.

性质:
1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)
2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

从1这点来看 红黑树是牺牲了严格的高度平衡的优越条件 为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

发表于 2016-09-24 17:43:41 回复(0)

huixieqingchun

JDK是红黑树的一个实现。

发表于 2016-05-11 19:39:31 回复(0)

牛客145381号

红黑树和avl树都属于自平衡二叉树；

两者查找、插入、删除的时间复杂度相同；

包含n个内部结点的红黑树的高度是o(logn);

TreeMap是一个红黑树的实现，能保证插入的值保证排序

发表于 2016-04-12 09:39:54 回复(0)

懒洋洋heart33

怎么觉得A也不正确呀

发表于 2015-09-11 16:16:23 回复(0)

yoghourt

对于A选项：

都是自平衡树

对于B选项：

AVL树种查找、插入和删除在平均和最坏情况下都是O（log n）

红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）与AVL相同。

对于D选项：

TreeMap是一红黑树，能保证插入的值保持排序。

发表于 2015-09-10 14:02:02 回复(0)

Established

BD

发表于 2015-09-09 15:50:48 回复(1)

binray

D,红黑树

发表于 2015-09-09 12:10:59 回复(0)

TaskMachine

我觉得C也不对吧，这个是小o(log(n))，应该是o(2log(n))才对

发表于 2015-09-08 22:12:57 回复(2)

TeamWE

JDK的TreeMap是用红黑树实现的，见：

http://www.ibm.com/developerworks/cn/java/j-lo-tree/

编辑于 2015-09-08 15:57:18 回复(0)

关于红黑树和AVL树，以下哪种说法不正确？

问题信息

热门推荐

相关试题