同样是"插入元素可能导致旋转",为什么RB树不是严格平衡,而AVL严格平衡?

zserewr

粗看RB树的讲解，这个树在构造/删除的过程中，像AVL一样可能会涉及旋转。
那么
1. 为什么RB树不是严格平衡的? 是因为旋转的方法不同吗?
2. 旋转方法不同，还是别的什么不同，导致了统计性能上RB树更好呢?

谢谢。

lxyscls

红黑树的特点
1、所有的分支上的黑节点个数相同（黑高度）
2、红节点的父节点不能为红节点

也就是说：最长的分支，是最短分支长度的两倍，只能是近似平衡

AVL不知道了

yulihua49

lxyscls 发表于 2015-12-31 20:27
红黑树的特点
1、所有的分支上的黑节点个数相同（黑高度）
2、红节点的父节点不能为红节点

AVL 就是完全平衡。查找速度比rb快。构建和析构慢。

windoze

因为这两种树的定义就是这样子啊，rbtree只要求每条路径上的黑节点个数相同，而且不能有两个连着的红结点，所以最长路径有可能达到最短路径的两倍长，AVL的定义就要求是一个严格的平衡树。
rbtree不用每次插入都做调整，而是攒够一批一次调整到位，所以对于频繁插入删除的情况下rbtree会稍快一点。单说查找性能rbtree肯定不会比avl更好。
统计意义上rbtree性能更好是因为绝大多数要用二叉树的场合插入和删除操作都比较多，要是没有太多插入删除就不用二叉树了，直接用个排序数组查找性能秒杀所有二叉树，虽说复杂度是一样的，但数组显然比二叉树更cache friendly，而且省内存。