红黑树和平衡二叉树的区别：
红黑树放弃了追求完全平衡 ， 追求大致平衡 ， 在与平衡二叉树的时间复杂度相差不大的情况下 ， 保证每次插入最多只需要三次旋转就能达到平衡 ， 实现起来也更为简单 。平衡二叉树追求绝对平衡 ， 条件比较苛刻 ， 实现起来比较麻烦 ， 每次插入新节点之后需要旋转的次数不能预知 。
文章插图
红黑树
红黑树是一种特定类型的二叉树 ， 是在计算机科学中用到的一种数据结构 ， 典型的用途是实现关联数组 。它是在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)是右子树的节点数量 。
推荐阅读
- 教学策略和教学 *** 的区别 教学策略和教学 *** 的区别是什么
- 教育方针和教育目的的区别 教育方针和教育目的的区别是什么
- 杏和什么放一起能够催熟 杏子不熟怎么催熟
- 木姜子花的养殖方法和注意事项
- 五子登科的养殖方法和注意事项
- 田赛和径赛的区别 田赛和径赛
- 果树修剪的最佳时间 果树修剪时间
- 黑蚂蚁养生酒的功效与作用 黑蚂蚁酒的功效和副作用
- 被动语态的用法 关于英语被动语态的详解和例句？
- 水瓶女和狮子男配吗 水瓶女和狮子男