Question

红黑树和平衡二叉树 区别

Answer 1

红黑树和平衡二叉树的主要区别如下：
平衡二叉树（AVL）树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而的英文旋转非常耗时的。所以平衡二叉树（AVL）适合用于插入与删除次数比较少，但查找多的情况。
红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log
n)。所以红黑树适用于搜索，插入，删除操作较多的情况。
扩展资料：
平衡二叉树在Windows
NT内核中广泛存在。
红黑树的应用：
1、在C
++的STL中，地图和集都是用红黑树实现的；
2、著名的Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3、IO多路复用的epoll的的的实现采用红黑树组织管理的sockfd，以支持快速的增删改查；
4、Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5、Java中的TreeMap中的实现。
参考资料：
百度百科-平衡二叉树
百度百科-红黑树

Answer 2

红黑树和平衡二叉树区别如下：
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
平衡二叉树又被称为AVL树（有别于AVL算法），且具有以下性质：它是一
棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法
平衡二叉树的常用算法有红黑树、AVL、Treap等。
最小二叉平衡树的节点的公式如下
F(n)=F(n-1)+F(n-2)+1
这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

Answer 3

红黑树属于平衡二叉树。
说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。
但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)，这有数学证明。所以它算平衡树，只是不严格。不过严格与否并不影响数据结构的复杂度。
红黑树多用于系统底层，oi竞赛中基本不用。