锐客网

  1. 首页 > 睿知 > >

红黑树算法效率分析,参考红黑树的寻址算法

经验分享睿知

红黑树which效率height，如果一个二叉查找树是红黑树，那么它的任何子树一定是红黑树 。为什么平衡二叉树需要红黑树 红黑树是二叉树和平衡二叉树的折中算法，两种代表性的平衡方法是AVL树和红黑树，B树，B -树，红黑树二叉排序树是空树或二叉树，具有以下性质:二叉排序树的数据操作效率: 1，Search效率O(logn)最好 ， O(logn)最坏 。2.Insert 效率与find -2相同/(先找到插入的位置 ， 只插入叶节点)；3.Delete 效率 O(logn) O(1)(仅左侧或右侧子树) ， O(logn) O(logn)(仅左侧和右侧子树同时存在)，平衡二叉树为空或者左右子树高度差的绝对值不超过1，左右子树都是平衡二叉树 。

1、php- 红黑树、散列表、跳表理解入门就是稍微修改一下链表的结构 。这个数据结构叫做效率，用来改进链表的查询 。如何让链表支持binary算法like array 是一种各方面性能都很优秀的动态数据结构，可以支持快速插入、删除和搜索操作 。Redis中的SortedSet是通过跳表实现的 。那Redis为什么选择使用跳表(和哈希表)来实现有序集合呢？

这个问题后面会回答 。让我们来看看跳表的数据结构 。其实概念很简单，就是我们不断往链表中插入数据的时候，如果不更新索引 ， 两个索引节点之间可能会有很多数据 。在极端情况下，跳转列表会退化为一个单独的链表 。红黑树，AVL树这样的平衡二叉树，通过左右旋转来维持左右子树的大小平衡，而跳表则是通过随机函数来维持平衡 。也可以完成插入、删除、搜索、迭代输出有序序列的操作，红黑树，时间复杂度与跳表相同 。
【红黑树算法效率分析,参考红黑树的寻址算法】
2、为什么HashMap使用 红黑树而不使用AVL树? 红黑树适合批量插入和删除；因为它是非严格平衡树；只要从根节点到叶节点的最长路径不超过最短路径的2倍，AVL树就是严格平衡的，最短路径和最长路径之差不能超过|1|，AVL允许差?。辉谥葱写罅康牟迦牒蜕境僮魇保?频繁的平衡调整会严重降低效率；红黑树虽然不是严格的平衡树，但还是平衡树；

AVL也登录了；；红黑树放弃了严格的平衡，从而可以插入、删除和搜索效率它在O(logn)中是稳定的 。回头看AVL树，O(logn)没有问题，但是为了保证高度平衡 ， 动态插入和删除的代价也增加了 。综合- 红黑树更好，Hashmap中使用的一些数据结构是数组和链表 ， 红黑树没有地址冲突时，效率O(1)有少量地址冲突，冲突的地址压缩(链表建立)，-2 。

    推荐阅读


    上一篇：wifi分析仪5G,WIFI分析仪,3.11.2无广告版

    下一篇：2017物联网行业分析,物联网ATX\/SSI行业分析