红黑树和平衡二叉树的区别 红黑树和平衡二叉树的区别是什么

红黑树和平衡二叉树的区别：

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

　　红黑树

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

　　平衡二叉树

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。最小二叉平衡树的节点总数的公式如下F(n)=F(n-1) F(n-2) 1这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

本文内容由互联网用户自发贡献，该文观点仅代表作者本人，因此内容不代表本站观点、本站不对文章中的任何观点负责，内容版权归原作者所有、内容只用于提供信息阅读，无任何商业用途。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站（文章、内容、图片、音频、视频）有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至353049283@qq.com举报，一经查实，本站将立刻删除、维护您的正当权益。