关于红黑树和 AVL 树,来自网络:
红黑树 并不追求 "完全平衡"——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。
红黑树能够以 O(n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较 "便宜" 的解决方案。红黑树的算法时间复杂度和 AVL 相同,但统计性能比 AVL 树更高。
当然,红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。
在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。
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 树更高.
霍夫曼树 必须是权值由小到大(由树叶到树根)!!!!
14 某一速率为 100M 的交换机有 20 个端口,其一个端口上连着一台笔记本电脑,此电脑从迅雷上下载一部 1G 的电影需要的时间可能是多久?
- 10S
- 20S
- 40S
- 100S
DE 交换机为独占带宽,即每个端口数据通过率为为最大 100Mb/s。注意单位是 Mb。因此最短时间为: 1GB/(100Mb/s)=1024MB/(12.5MB/s)=81.92s。 10 请问下列代码的输出结果有可能是哪些()?
- 200S
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
- 2015,
- 810大端big - endian
- 50810,
- 201
- 810,
- 2015小端little - endian
4 以下不属于 tcp 连接断开的状态是?
- 20150,810
- TIME_WAIT
- FIN_WAIT_1
- SYNC_SENT
- FIN_WAIT_2
- 、
- 、、毕竟开始建立连接也不能算是断开的啊!!!!!!!
- 1.自身对其(截止的长度是自身类型长度的整数倍)
- 2.整体对齐 (最长的类型 或者 parama pack指定的字节数)
来源: http://www.bubuko.com/infodetail-1948877.html