Why is Red Black Tree slower than linear search? Is it because of the test case?!


  • 0
    C

    Theoretically we can use map to optimize the search process, but why it is still slower than linear search? Is it because of the test case?! The map should be like binary search, right? But the result show that the first(linear search) is 24ms and the second(using map) is 40ms.

    First:

    ListNode* insertionSortList(ListNode* head) {
        ListNode sentinel(0), *prev = nullptr, *cur = head;
        while (cur) {
            if (!prev || !prev->next || prev->next->val > cur->val) prev = &sentinel;
            while (prev->next && prev->next->val < cur->val) {
                prev = prev->next;
            }
            ListNode *tmp = cur->next;
            cur->next = prev->next;
            prev->next = cur;
            cur = tmp;
        }
        return sentinel.next;
    }
    

    Second:

    ListNode* insertionSortList(ListNode* head) {
        ListNode sentinel(0), *cur = head;
        map<int, ListNode*> cache;
        cache[INT_MIN] = &sentinel;
        while (cur) {
            ListNode *p = (--cache.upper_bound(cur->val))->second;
            cache[cur->val] = cur;
            ListNode *tmp = cur->next;
            cur->next = p->next;
            p->next = cur;
            cur = tmp;
        }
        return sentinel.next;
    }
    

    Is it because of the test case?!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.