CODEWITHSUNDEEP
c++
Joe Cool
Joe Cool

Reputation: 207

Word Processing Application

I'm trying to implement a data structure that allows me to look up a number in a database as quickly as possible. Let's say I have a database that has 5450 different numbers. My primary concern is speed not memory efficiency. I found this article online about Multi Way Tree: http://c0.typesafety.net/courses/15122-f10/lectures/18-tries.pdf. So I decided to implement a 10-way tree where each node is an array size 10 but I'm having a bit of difficulty how to create classes for the structure. Here is a rough outline that I came up with: 

class MSTNode{
  bool isDigit; //is it one of the digit in the number
  int arrayNode[];

  MST(bool isWord): isWord(isWord){
    arrayNode[] = [0,1,2,3,4,5,6,7,8,9];
  }
}


class MST{
  MSTNode * root;

  //What functions should be included in this class?
 //Insert Function?
 //Search Function?
}

I just need a little help to get the ball rolling. I would appreciate very much if somebody can point out the potential problem with my design above. What should be included? what should not? Basically, I need help to come up with the design of the data structure. In no way, I'm looking to get free code from you. I just need help in the beginning with the design, I can implement the rest.

Upvotes: 1

Views: 102

Answers (1)

Jarod42
Jarod42

Reputation: 217810

You may have something like:

class MSTNode{
public:
    void Insert(unsigned int n) {
        // GetOrCreate MSTNode in the first digit of n
        // and recursively call insert with n without this digit
        // once no more digit, set the isFinal flag.
    }

    bool Search(unsigned int n) const {
        // Get MSTNode of the first digit of n
        // if nullptr, return false.
        // and recursively call Search with n without this digit
        // once no more digit, return the isFinal flag.
    }

private:
  std::unique_ptr<MSTNode> arrayNode[10];
  bool isFinal = false; //is it one of the digit in the number
};

With the first MSTNode the root.

Upvotes: 1

Related Questions