c++ - 为什么我的排名二叉搜索树实现如此缓慢？

Question

所以我写了一个 Ranked 自平衡二叉搜索树，而不是使用 std::set。我期待它能够更快地获得元素的排名，但它似乎比使用 std::set 并迭代查找排名要花费更多时间。有什么办法可以加快速度吗？

#include<bits/stdc++.h>

struct treeNode{
    int data;      
    int leftsize;  //for finding rank
    int height;    //for balancing during insertions and deletions

    treeNode* left;
    treeNode* right;

    treeNode()
    :data(NAN), leftsize(0), left(nullptr), right(nullptr){}

    treeNode(int val, int lsize, int ht)
    :data(val), leftsize(lsize), height(ht), left(nullptr), right(nullptr){}
};

int height(treeNode* node)
{
    if(node == nullptr)
        return 0;
    
    return node->height;
}

int getBalance(treeNode* node)
{
    if(node==nullptr)
        return 0;
    
    return height(node->left) - height(node->right);
}


int parseLeftSub(treeNode* node)
{
    if(node == nullptr)
        return 0;
    int cnt = 1;
    cnt += parseLeftSub(node->left);
    cnt += parseLeftSub(node->right);
    
    return cnt;
}

void printNode(treeNode* node)
{
    if(node ==  nullptr)
        return;
    
    printNode(node->left);
    std::cout << node->data << "  " << node->leftsize << std::endl;
    printNode(node->right);
}

treeNode* createNode(int val)
{
    treeNode* node = new treeNode(val, 1, 1);
    return node;
}

treeNode* createTree(std::vector<int>& a, int start, int end)
{
    if(start>end)
        return nullptr;

    int mid = (start + end)/2;

    treeNode* node = createNode(a[mid]);
    node->left = createTree(a, start, mid-1);
    node->right = createTree(a, mid+1, end);

    node->leftsize += parseLeftSub(node->left);

    return node;
}

treeNode* rightRotate(treeNode* y)  
{  
    treeNode* x = y->left;
    treeNode* T2 = x->right;
  
    // Perform rotation  
    x->right = y;  
    y->left = T2;  
  
    // Update heights  
    y->height = std::max(height(y->left), 
                    height(y->right)) + 1;  
    x->height = std::max(height(x->left), 
                    height(x->right)) + 1;  
  
    // Return new root
    y->leftsize = parseLeftSub(y->left) + 1;
    return x;  
}

treeNode* leftRotate(treeNode* x)  
{  
    treeNode* y = x->right;  
    treeNode* T2 = y->left;  
  
    // Perform rotation  
    y->left = x;  
    x->right = T2;  
  
    // Update heights  
    x->height = std::max(height(x->left),     
                    height(x->right)) + 1;  
    y->height = std::max(height(y->left),  
                    height(y->right)) + 1;  
  
    // Return new root
    y->leftsize = parseLeftSub(y->left) + 1; 
    return y;  
}  

treeNode* insertNode(int val, treeNode* node)
{
    if(node == nullptr)
        return createNode(val);

    if(val < node->data)
        node->left = insertNode(val, node->left);
    else if(val > node->data)
        node->right = insertNode(val, node->right);
    else
        return node;
    
    node->height = 1 + std::max(height(node->left), height(node->right));
    node->leftsize = parseLeftSub(node->left) + 1;
    
    int balance = getBalance(node);

    if(balance > 1 && val < node->left->data)
        return rightRotate(node);
    
    else if(balance < -1 && val > node->right->data)
        return leftRotate(node);
    
    else if(balance > 1 && val > node->left->data)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    
    else if(balance < -1 && val < node->right->data)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

treeNode* searchNode(int val, treeNode* node)
{
    if(node == nullptr)
        return nullptr;
    
    treeNode* foundNode = nullptr;
    if(val == node->data)
        return node;

    else if(val < node->data)
        foundNode = searchNode(val, node->left);
    else
        foundNode = searchNode(val, node->right);
    
    return foundNode;
}

treeNode* findLowerBound(int val, treeNode* node)
{
    if(node == nullptr)
        return nullptr;
    
    if(val == node->data)
        return node;

    else if(val>node->data)
    {
        return(findLowerBound(val, node->right));
    }

    treeNode* temp = findLowerBound(val, node->left);
    if(temp != nullptr && temp->data >= val)
        return temp;
    else
        return node; 
}

treeNode* findUpperBound(int val, treeNode* node)
{
    if(node == nullptr)
        return nullptr;
    
    if(val == node->data)
        return node;

    else if(val<node->data)
    {
        return(findUpperBound(val, node->left));
    }

    treeNode* temp = findUpperBound(val, node->right);
    if(temp != nullptr && temp->data <= val)
        return temp;
    else
        return node; 
}

treeNode* findMinNode(treeNode* node)
{
    if(node->left == nullptr)
        return node;
    return (findMinNode(node->left));
}

treeNode* deleteNode(int val, treeNode*& node)
{
    if(node == nullptr)
        return nullptr;

    if(node->data > val)
        node->left = deleteNode(val, node->left);
    else if(node->data < val)
        node->right = deleteNode(val, node->right);
    else
    {
        if(node->left==nullptr && node->right==nullptr)
        {
            delete node;
            node = nullptr;
        }

        else if(node->left==nullptr)
        {
            treeNode* temp = node;
            node = node->right;
            delete temp;
        }
        else if(node->right==nullptr)
        {
            treeNode* temp = node;
            node = node->left;
            delete temp;
        }
        else
        {
            treeNode* temp = findMinNode(node->right);
            node->data  = temp->data;
            node->right = deleteNode(temp->data, node->right);
        }
    }    

    if (node == NULL)  
        return node;
    
    node->leftsize = parseLeftSub(node->left) + 1;
    node->height = 1 + std::max(height(node->left),  
                           height(node->right));  

    int balance = getBalance(node);  
  
    if (balance > 1 &&  
        getBalance(node->left) >= 0)  
        return rightRotate(node);  
  
    if (balance > 1 &&  
        getBalance(node->left) < 0)  
    {  
        node->left = leftRotate(node->left);  
        return rightRotate(node);  
    }  

    if (balance < -1 &&  
        getBalance(node->right) <= 0)  
        return leftRotate(node);  

    if (balance < -1 &&  
        getBalance(node->right) > 0)  
    {  
        node->right = rightRotate(node->right);  
        return leftRotate(node);  
    }  
    
    return node;
}

int findRank(int val, treeNode* node)
{
    int rank = node->leftsize;
    if(node==nullptr)
    {
        return -1;
    }

    if(val<node->data)
    {
        rank -= node->leftsize;
        rank += findRank(val, node->left);
    }
    else if(val>node->data)
    {
        rank += findRank(val, node->right);
    }

    return rank;    
}

我知道它很多。也可以使用任何其他 stl 容器来有效地查找排名、插入和删除

标签： c++performancec++11binary-search-tree