数据结构和算法 - 关于红黑树和链表的疑问

问题描述

问 题

为什么红黑树比链表结构的性能要差很多，但是STL的中map和set等都是用红黑树实现？

        // 实例化红黑树
        var rbTree = new RBTree();
        // 开始插入数据1w条数据
        console.time('RB_insert');
        for (var i = 0; i < 10000; i++) {
            rbTree.insertNode(i + '_test');
        }
        // 插入结束 输出插入时间：
        console.timeEnd('RB_insert');
        
        // 实例化链表结构
        var linkedList = new LinkedList();
        // 开始插入1w条数据
        console.time('linkedList_insert');
        for (var i = 0; i < 100; i++) {
            linkedList.add(i + '_test');
        }
        // 插入结束 输出插入时间：
        console.timeEnd('linkedList_insert');
        
        
        // 开始检索指定数据
        console.time('RB');
        var node = rbTree.searchNode(9999);
        // 输出用时
        console.timeEnd('RB'); 
        
        // 开始检索指定数据
        console.time('linkedList');
        var _node = linkedList.searchNode(9999);
        // 输出用时
        console.timeEnd('linkedList');

既然链表结构性能比红黑树高这么多，但是还是STL还是用的红黑树。能否列举出试用红黑树的理由哪？

点击查看源码

解决方案

比较速度不是这么比较的啊同学……
只取一个数算什么啊，所以我把0~9999都取了一遍，这是结果

另外虽然查询时红黑树在渐进意义上是O(nlgn)，链表是(n^2)，但是红黑树常数大啊，所以我把10000改成了20000

再大我电脑就不撑了，不过你可以试试
PS.我没看你的实现，我默认红黑树插入为O(lgn),查询为O(lgn)，链表插入为O(1)，查询为O(n)
PPs.在原本代码的条件下，红黑树总的时间复杂度为O(nlgn)+O(lgn)=O(nlgn)，链表为O(n)+O(n)=O(n)，当然是链表快了2333(红黑树本来就是用在大量的动态的添加删除查询的环境下的

这篇关于数据结构和算法 - 关于红黑树和链表的疑问的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！