1 Replies - 4223 Views - Last Post: 15 August 2012 - 04:05 AM

#1 shivani2691  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 15-August 12

reading file data to a bst

Posted 15 August 2012 - 03:07 AM

I am making a dictionary in C lang.have used BST to store and search data.the code is adding and searching fine.but as soon as i restart my application , the search fails,since tree is initialised every time.olso file stores data sequentially not in a tree format.so i will have to reaload the entire file data to build a tree,which is inefficient.so how do i tackle this.my main objective is to make searching as efficient as possible..
Is This A Good Question/Topic? 0
  • +

Replies To: reading file data to a bst

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3160
  • View blog
  • Posts: 9,532
  • Joined: 05-May 12

Re: reading file data to a bst

Posted 15 August 2012 - 04:05 AM

By BST, I'm assuming that you mean binary search tree. Is your tree balanced or mostly balanced?

Irregardless whether the tree is balanced or not, you can save the tree in a cache file. The next time your program starts, compare the time stamp of the cache as compared to the dictionary. If the the cache is newer, load the tree from the cache. If the dictionary is newer, you might as well build a tree from the dictionary from scratch. You could still load from the cache, and do search and inserts, but now you'll be doing double traversals unless you have a InsertIfNotPresent() function for your tree.

The question about balance vs. not balance tree comes up because if you have a balanced tree, you can have the cache file be laid out like an array.
[code]
|Node0|Node1|Node2|Node3|Node4|Node5|Node6|...|Node(2N+1)|
[code]
And take advantage of the property that a binary tree can be store in an array where a parent node is in index i, left child is in index 2*i, and right child is in index 2*i+1. Denote a null pointer as using index value 0 as stored in the node location. This will let you quickly rebuild a tree top down without all the insertion traversals.

If it's not balanced, you can save the the tree node values in pre-order along with indicators whether there is a left, right, or both child node. Rebuilding the tree is a also a matter of reading the file, and determining which node needs to be allocated and loaded next.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1