关于红黑树和链表的疑问

Question

为什么红黑树比链表结构的性能要差很多，但是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还是用的红黑树。能否列举出试用红黑树的理由哪？

点击查看源码

Answer 1

首先红黑树内元素的顺序取决于元素的值,链表的顺序取决于元素插入的顺序,红黑树插入是O(logn)的,链表插入末尾是O(1)的,所以插入同样数目的节点链表性能表现好一些,但是插入完成以后红黑树是有序的,遍历红黑树可以顺序或逆序输出所有元素,搜索红黑树也只要O(logn),而搜索链表要O(n),红黑树明显优于链表
楼主测出来链表搜索的时间短是因为楼主测试用例里面链表包含的元素数比红黑树少

Answer 2

测试过乱序吗？

Answer 3

红黑树复杂度 O(logn) 级别的吧，链表复杂度 O(n) 吧。

Answer 4

比较速度不是这么比较的啊同学……
只取一个数算什么啊，所以我把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(红黑树本来就是用在大量的动态的添加删除查询的环境下的