Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

Complexity of the search

Sign in to follow this  


Thanks to jollyjeffers I've managed to increase my path search speed to O(xlogn). He mentioned in my previous posting that a friend of his had implemented an archive with a binary search tree O(logn) in the header for fast file access. This would be especially necessary as the archive grew in size. This got me thinking.

What I came up with...

My directory is stored in an n-array tree. What I decided to do is implement binary searches at each node in the tree. Remember here each node represents a folder. Within each node there is a list of sub folder references and a list of file references. So if the current location is in the root and I wanted to access path "B\F\I\K\N\File.bin" then the search will need to first search the root node for a sub folder named B then move to B folder and search for F then move to F etc. until the N folder is reached and a search of that folders files will find the desired file. You can see a diagram I made of this particular search to get a better idea.

Each list needs to be sorted for a binary search to work so this is done every time a new item is added to either of the two lists. What this all works out to is a search time of O(xlogn) where n is the total number of items searched and x is the number of searches made which is also the number of nodes traversed in the operation. This seems like an acceptable complexity to me as long as x doesn't become too large and it shouldn't since x corresponds to the height of the tree. Like I said I've never done this before and there is probably better ways to do this. I'm not above just scrapping it all and starting over if someone can tell me why. [smile]
Sign in to follow this  


Recommended Comments

No arguments here with binary search trees. Also makes it easy to traverse the entire list using recursion.

Share this comment

Link to comment
OK.. So are you saying that instead I should use a binary search tree rather than the N-ary tree? The problem I have with just using a list of files and a binary search tree is keeping the directory structure. How could I store a complete directory inside of a binary tree? I want to keep the directory structure so that if I want to have 10 different files named "KabFlax.bup" in 10 different folders then it's cool.

Share this comment

Link to comment
Sorry, I meant n-ary tree. I guess the only way you could have it in a binary tree is to give each node the full path and filename, that way it would be sorted by directory by itself and you could have same name files, but it would be no good if you wanted to change anything.

Share this comment

Link to comment
Thanks for the clarification. I've been mulling over doing just that. I was thinking of storing both trees in the header file one for directory and one for path searches. It would then perform two searches for one search. One to find the folder and one to file in that folder path. This way I would only need to keep a sorted list of the folder paths with references to individual nodes in the directory tree. It would be more data to save but it would improve my searches to O(logn). I'll just forget it for now. If I want to change it later then it shouldn't be a problem. Thanks for the input.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!