Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
红黑树
Java 集合系列之 TreeMap详细介绍(源码解析)和使用示例
代码来自算法第四版
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树实际上是由2-3-4树转换而来，红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
平衡二叉树
在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。
AVL树的定义:
一棵AVL树满足以下的条件:
1>它的左子树和右子树都是AVL树
2>左子树和右子树的高度差不能超过1
性质:
1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)
2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n))。
为了保证平衡，AVL树中的每个结点都有一个平衡因子，它表示这个结点的左、右子树的高度差，AVL树上所有结点的平衡因子值只能是-1、0、1。
红黑树，平衡二叉树对比
- 红黑树 非严格平衡；平衡二叉树严格平衡。
- 红黑树结点额外空间 2bit(Red,Black);平衡二叉树结点额外空间3bit(-1,0,1)。
- 红黑树更新旋转次数，插入最多2次，删除最多3次；平衡二叉树因为严格平衡，插入最多2次，删除可达O（n），被删除结点以上父节点皆有可能旋转。
- 红黑树查询耗时要比平衡二叉树多
建议使用场景
- 如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
- 如果操作序列完全随机，没有任何关系，建议使用普通二叉树BST。
- 如果操作序列存在一定关系，建议使用红黑树。
- 如果操作序列完全有序，建议使用平衡二叉树。
- 如果操作序列存在局部性，建议使用Splay伸展树。
具体分析，斯坦福有专门的论文分析了BST，AVL,RB Tree,Splay的性能。
Performance Analysis of BSTs in System Software](http://benpfaff.org/papers/libavl.pdf)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/180173.html原文链接：https://javaforall.net
