This paper presents a new internal Searching Algorithm used for processing a particular integer data from Random Access Memory (RAM). The incoming data are arranged like a tree structure which makes the search simpler by reducing the number of comparisons made than the comparisons involved in a Binary Search tree. The arrangement of the data fall on basic mathematical classification of the number system. The tree arrangement will start as the user starts giving the data one by one or with the help of a file. It overcomes the limitations of the Binary Search Tree (BST). The data are reduced to its simpler form and divided into levels depending on the place value of each digit in the data. Once the data are arranged, searching process starts and tracing path will be in correct order like BST, as the input data is given for search. The maximum number of comparisons is decided by the largest number's digits in the list and not merely on the total number of data's.
Keywords: internal searching algorithm, Binary search tree
This algorithm is used only for processing the numeric data and it comes under the classification of Internal Searching Technique and has the following merits:
- Data distribution can be in any order.
- Total Comparisons is decided by the largest numbers digit's.
- Since the data's are arranged according to a simple classification of number system, there is no chance for moving in a wrong path when the searching is done.
- Time for the operation can be calculated in the initial stage itself.
II. TREE FORMATION
Whenever the data comes, the data is classified as positive or negative domain. Then further, the number is classified as an odd integer or and even integer in that domain. The first step of classification ends here. Then the present data should undergo a modulo operation with 10 and the digit which is coming out after modulo operation will be classified as odd or even and placed in a structure which is formed dynamically at that instance and all the self-referential structure of the presently created structure will be made NULL and this is calculated to be the first stage , further the data is divided by 10 till it encounters zero. Then number is further spitted if any , and the next digit which is got by modulo division , dynamically the memory is allocated to it and the digit is stored & that digit is categorized as odd or even and the recently created structure address is taken to the previous structure memory's odd or even self-referential structure and in every stage the status flag of the corresponding created structure will be zero and will be made one to the last stage structure when the number can't be further splitted.
When the data to be searched is got, it is first categorized into positive or negative domain and further as odd or even domain. After setting the path, the number to be searched undergoes modulo operation by 10 and checked whether the particular digit is present in the categorized list in that stage in the tree. If the digit is not present, then user will be intimated with a information that data not found and the program will be exited. If the digit is there in the list, then data will undergo further modulo operation and checked for next digit to be in even or odd category and the corresponding path or address will be taken from the present structure member. If the member has NULL in it, the user will be intimated with proper information that data not found or the process repeats till the given data reaches zero by dividing by ten.
Here 872 is got from the user for searching , first this number is classified into positive or negative , here being positive the address stored in the corresponding self-referential structure and after getting the address , it is further checked for odd or even category , here it is an odd number . So the corresponding address will be fetched from the structure member and the number undergoes modulo operation for getting the last digit and number is divided by 10. Then that is checked with the list present in the stage 1 as mentioned in figure 1 in red colour squares. The number 2 is present in the list , then the present number will undergo modulo division and further gets split up and checked for odd or even category and the corresponding address will be fetched from the structure. In the travel path, if any digit is even or odd in the category positive or negative is NULL, then the corresponding information that data not found will be intimated to the user. If it is not NULL, same steps are repeated as above till the number can't be further divided.If the last digit is found in the path travelled successfully, then the status flag present in that present node is checked. If it is one, the data is successfully found or not found will be intimated to the user.
Space Complexity: memory used is very large in the arrangement.
Retrieval of data : once the data are arranged it can't be retrieved back in the same order.
Note: worst behaviour for very small data. It cannot handle Hexadecimal values.
In the worst case, in every stage the amount of memory used will be increasing in multiples of 5.
The complexity graph can be traced as 5a . The time complexity is of logarithmic order.
The inference of this algorithm is that it overcomes the limitations of the binary search tree and reduces the number of comparisons made for huge sets of data given in any order.
However the memory taken is high, the performance of this technique is fast compared to binary search tree or any other searching techniques used for numeric search.
- Yashwanth K Kanethker, Data Structures through C, 6th ed., BPB publications, New Delhi.
- Yashwanth K Kanethker, understanding pointers in C, 3rd ed., BPB publications, New Delhi.
- (2002) The IEEE website. [Online]. Available: http://www.ieee.org/
- Wikipedia search [Online]. Available: http://www.wikipedia.org//
- Webopedia search [Online]. Available: http://www.webopedia.com//