[Cracking The Coding Interview] Chapter 11.08

 

#include <iostream>
#include <stdlib.h>
#include <vector>

class BST
{
public:
    BST() : ptr(NULL){}

    void insert(int data)
    {
        ptr = insert(ptr, data);
    }

    int getRank(int data)
    {
        return getRank(ptr, data);
    }

private:
    struct Node
    {
        int data;
        int leftsize;
        int rightsize;
        Node* left;
        Node* right;
        Node(int val) : data(val), leftsize(0), rightsize(0), left(NULL), right(NULL){}

    };
    int getRank(Node* root, int data)
    {
        if(root==NULL)
            return 0;
        else if(data == root->data)
            return root->leftsize;
        else if(data < root->data)
        {
            if(root->left==NULL)
                return -1;
            int val = getRank(root->left, data);
            return val==-1? -1 : val;
        }
        else //if(data > root->data)
        {
            if(root->right==NULL)
                return -1;
            int val = getRank(root->right, data);
            return val==-1 ? -1 :  (root->leftsize + 1 + val );
        }
    }

    Node* insert(Node* root, int data)
    {
        if(!root)
            return new Node(data);
        if(data<=root->data)
        {
            root->left = insert(root->left, data);
            root->leftsize  ;
        }
        else
        {
            root->right = insert(root->right, data);
            root->rightsize  ;
        }
        return root;
    }

    Node* ptr;
};



int main()
{
    BST bst;
    std::vector<int> stat(10,0);
    for(int i=0; i<20; i  )
    {
        int data = rand()%10;
        bst.insert(data);
        stat[data]++;
    }

    int result;
    bool test;
    for(int i=0; i<10; i  )
    {
        result = bst.getRank(i);
    }

    return 0;
}