红黑树和平衡二叉树有什么区别？

红黑树放弃追求完全平衡，追求近似平衡。在时间复杂度与平衡二叉树相差不大的情况下，每次最多只需三次旋转，就更容易达到平衡。平衡二叉树追求绝对平衡，条件苛刻，实现麻烦，插入新节点后需要旋转的次数不可预知。

红色黑色的树

红黑树是二叉树的一种特定类型，是计算机科学中使用的一种数据结构，其典型用途是实现关联数组。它是RudolfBayer在1972年发明的，他称之为“对称二叉B树”。它的现代名称是在莱奥伊写的一篇论文中获得的。1978的Guibas和RobertSedgewick。它是复杂的，但是它的操作具有良好的最坏情况运行时间，并且在实践中是高效的。它可以在O(logn)时间内找到、插入和删除，其中n是树中元素的个数。

平衡二叉树

Self-Self-balancing binarysearchtree也叫AVL树(不同于AVL算法)，具有以下性质:它是一棵空树或其左右子树高度差的绝对值不超过1，左右子树都是平衡二叉树。平衡二叉树常见的实现方法有红黑树、AVL、替罪羊树、Treap、扩展树等。最小二叉平衡树的节点总数公式如下:F(n)= f (n-1)+F(n-2)+1，类似于递归序列，可以参考斐波那契序列，其中1为根节点，F(n-65438+)。